foldr 没有返回无限列表

Question

我已阅读 https://www.haskell.org/haskellwiki/Foldl_as_foldr 和其他几篇关于 foldl 和 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 时，该功能不会 return。我认为 foldr 是主体递归的，允许您在这些类型的情况下将它与无限列表一起使用。为什么这不适用于我的解决方案？

Answer 1

问问自己：哪个斐波那契数列会排在列表的第一位？我对你的代码的阅读是，这个问题的答案是 "the biggest one"（理论上，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]

foldr 没有返回无限列表

foldr not returning with an infinite list

recursion

haskell

lazy-evaluation