如果「輸出」值與迭代的值不同，前奏的迭代的替代方法是什麼？

Question

我碰到過一種模式，我從種子值x開始，並在每一步生成一個新的種子值和一個要輸出的值。我期望的最終結果是輸出值的列表。

my_iter :: (a -> (a, b)) -> a -> [b] 
my_iter f x = y : my_iter f x' 
    where (x',y) = f x 

並使用此會產生Fibonacci數的一個人爲的例子：

fibs:: [Integer] 
fibs = my_iter (\(a,b) -> let c = a+b in ((b, c), c)) (0,1) 
-- [1, 2, 3, 5, 8... 

我的問題是，我有這種感覺，有非常這可以通過下面的函數來表示可能是更習慣於這樣做的方式。什麼是我的功能的慣用替代方案？

我現在能想到的唯一一個涉及Prelude的iterate，但它們有一些缺點。

的一種方法是首先遍歷和地圖後

my_iter f x = map f2 $ iterate f1 x 
    where f1 = fst . f 
      f2 = snd . f 

然而，這看起來很醜陋，如果沒有分裂成˚F單獨F1和F2的功能自然的方式。 （在設計好的斐波那契情況下，這很容易做到，但是在某些情況下，生成的值不是種子的「獨立」功能，因此它不是那麼容易分割的東西）

另一種方法是將元組「輸出」的價值觀與種子一起，並使用單獨的步驟將它們分開（有點像「的Schwartzian變換」排序的東西）：

my_iter f x = map snd . tail $ iterate (f.fst) (x, undefined) 

但這似乎奇怪，因爲我們要記住忽略生成的值以獲得種子（第（f.fst）位）並添加我們需要的第一個虛擬生成值的「未定義」值。

Answer 1

如前所述，您需要的功能是unfoldr。顧名思義，這與foldr恰恰相反，但確切地說明爲什麼這可能是有益的。下面是foldr類型：

(a -> b -> b) -> b -> [a] -> b 

的前兩個參數是獲得b類型的東西的方式，以及對應於兩個數據構造函數列表：

[] :: [a] 
(:) :: a -> [a] -> [a] 

...每次出現在那裏[a]被替換爲b。注意[]案例產生的b沒有輸入，我們可以將這兩個合併爲一個函數，將Maybe (a, b)作爲輸入。

(Maybe (a, b) -> b) -> ([a] -> b) 

額外的圓括號表明，這基本上是一種將一種轉換轉換爲另一種轉換的功能。

現在，簡單地反向兩個變換的方向：

(b -> Maybe (a, b)) -> (b -> [a]) 

結果是準確的unfoldr類型。

這個演示的基本思想也可以類似地應用於其他遞歸數據類型。

Answer 2

您正在查找的標準功能稱爲unfoldr。

Answer 3

另一種可能性是在State單子iterateM：

iterateM :: Monad m => m a -> m [a] 
iterateM = sequence . repeat 

它不是標準庫，但它很容易建立。

所以你my_iter是

evalState . sequence . repeat :: State s a -> s -> [a] 

Answer 4

Hoogle在這種情況下非常有用的工具，因爲它的名字並不只支持搜索功能，還按類型。

在你的情況，你想出了所需的類型(a -> (a, b)) -> a -> [b]。輸入它不會產生任何結果 - 嗯。

好吧，也許有一個標準函數，語法略有不同。例如，標準函數可能有其參數翻轉;讓我們尋找(a -> (a, b))在其類型簽名的地方。這次我們很幸運，因爲有很多結果，但所有這些都是異國情調的包裝，沒有一個看起來很有幫助。

也許你的函數的第二部分是一個更好的匹配，畢竟你想從一些初始元素生成一個列表 - 所以輸入a -> [b]並點擊搜索。第一個結果：unfoldr - 賓果！