Haskell中自定义斐波那契函数无法适配惰性求值的问题咨询

首先先把你的代码贴出来方便咱们分析：

infFib :: [Integer]
infFib = infFib' [] 
  where 
    infFib' [] = infFib' [0,1] 
    infFib' (xs) = infFib' (xs ++ [(foldr (\a b -> a+b) 0 (take 2 (reverse xs)))])

问题出在哪里？ #

你的代码没法在惰性求值下正常工作，核心原因有两个：

• 列表构建方式违背惰性求值逻辑：你每次用xs ++ [新元素]来扩展列表。Haskell的列表是单链表，++操作需要遍历整个左列表才能完成——更关键的是，这种方式要求必须生成完整的前序列表才能得到下一个元素，而惰性求值的核心是"按需生成"，不需要提前构建全部内容。当你尝试取infFib的前几个元素时，系统不得不反复构建越来越长的完整列表，效率极低甚至会陷入无法推进的递归循环。
• 回溯式取元素效率低下且不符合惰性要求：你用reverse xs >> take 2来获取最后两个元素求和，这又是一个O(n)的操作——每次生成新元素都要遍历整个列表到末尾，对于无限列表来说，这种回溯式的逻辑完全没法正常工作，因为你永远没法"到达"一个无限列表的末尾。

正确的惰性实现方式 #

咱们可以用两种更符合Haskell惰性特性的写法来实现无限斐波那契数列：

方法1：利用zipWith的优雅写法

这是Haskell社区里最常用的无限斐波那契数列实现：

infFib :: [Integer]
infFib = 0 : 1 : zipWith (+) infFib (tail infFib)

• 先直接给出前两个元素0和1，不需要任何计算；
• zipWith (+) infFib (tail infFib)会把infFib和它的尾部（从1开始的列表）对应位置的元素相加：第三个元素是0+1=1，第四个是1+1=2，第五个是1+2=3，以此类推；
• 这种写法完全是"向前推进"的，每一个新元素只依赖前面已经生成的元素，惰性求值可以按需生成任意数量的元素，不会有多余的计算。

方法2：跟踪状态的递归写法

如果你更倾向于用递归辅助函数的方式，可以让辅助函数直接跟踪最后两个斐波那契数，而不是整个列表：

infFib :: [Integer]
infFib = infFib' 0 1
  where
    infFib' a b = a : infFib' b (a + b)

• infFib'每次接收前两个数a和b，先输出a，然后递归调用时把b作为新的a，a+b作为新的b；
• 每次生成新元素只需要O(1)的计算，完全符合惰性求值的"按需生成"特性，你取多少元素就生成多少，没有任何回溯或多余操作。

总结 #

你的代码核心问题是依赖整个列表来生成下一个元素，而不是只跟踪必要的状态（最后两个斐波那契数），这导致它无法利用Haskell惰性求值的优势，甚至无法正常生成无限列表。换成上面两种写法，就能完美解决这个问题啦。

内容的提问来源于stack exchange，提问作者james king