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]