foldr無法返回無限列表

Question

我讀過https://www.haskell.org/haskellwiki/Foldl_as_foldr以及其他一些關於foldl和foldr之間區別的博客文章。現在我想要寫的斐波那契序列與foldr相似的無限名單，我已經想出了以下解決方案：

fibs2 :: [Integer] 
fibs2 = foldr buildFibs [] [1..] 
    where 
    buildFibs :: Integer -> [Integer] -> [Integer] 
    buildFibs _ [] = [0] 
    buildFibs _ [0] = [1,0] 
    buildFibs _ l@(x:s:z) = (x + s):l 

但是當我做take 3 fibs2，該函數不返回。我認爲foldr是body遞歸的，可以讓你在這些類型的情況下將它與無限列表一起使用。爲什麼這不適合我的解決方案？

Answer 1

問問你自己：哪個斐波納契數是列表中的第一個？我對你的代碼的閱讀是，這個問題的答案是「最大的一個」（從概念上講，buildFibs的每次迭代都會在結果列表的頭部添加一個稍大的數字）。由於有無限多的斐波納契數字，這需要一段時間來計算！

Answer 2

這是等式推理一個偉大的運動：

fibs2 = foldr buildFibs [] [1..] 

foldr f z [] = z 
foldr f z (x:xs) = f x (foldr f z xs) 

foldr buildFibs [] [1..] = 
    buildFibs 1 (foldr buildFibs [] [2..]) = 
    buildFibs 1 (buildFibs 2 (foldr buildFibs [] [3..])) = 
    buildFibs 1 (buildFibs 2 (buildFibs 3 (foldr buildFibs [] [4..]))) = 
    ... 

我希望現在你可以看到這個問題：foldr試圖返回之前遍歷整個列表。如果我們用foldl代替，會發生什麼？

foldl f z [] = z 
foldl f z (x:xs) = foldl f (f z x) xs 

buildFibs' = flip buildFibs 

foldl buildFibs' [] [1..] = 
    foldl buildFibs' (buildFibs 1 []) [2..] = 
    foldl buildFibs' [0] [2..] = 
    foldl buildFibs' (buildFibs 2 [0]) [3..] = 
    foldl buildFibs' [0,1] [3..] = 
    foldl buildFibs' (buildFibs 3 [0,1]) [4..] = 
    foldl buildFibs' (0+1 : [0,1]) [4..] = 
    foldl buildFibs' [1,0,1] [4..] = 
    foldl buildFibs' (buildFibs 4 [1,0,1]) [5..] = 
    foldl buildFibs' (1+0 : [1,0,1]) [5..] = 
    foldl buildFibs' [1,1,0,1] [5..] = 
    foldl buildFibs' (buildFibs 5 [1,1,0,1]) [6..] = 
    foldl buildFibs' [2,1,1,0,1] [6..] = 
    -- For brevity I'll speed up the substitution 
    foldl buildFibs' [3,2,1,1,0,1] [7..] = 
    foldl buildFibs' [5,3,2,1,1,0,1] [8..] = 
    foldl buildFibs' [8,5,3,2,1,1,0,1] [9..] = 
    ... 

所以，你可以看到你其實可以計算使用buildFibs和foldl的斐波那契數，但不幸的是你向後構建他們的無限列表，你將永遠無法在計算特定元素因爲foldl永遠不會終止。你可以計算它們的有限數量：

> take 10 $ foldl buildFibs' [] [1..10] 
[34,21,13,8,5,3,2,1,1,0]