斐波那契函数的惰性评估

Question

我在 Haskell 中编写了下面的函数，但我不太清楚为什么它不适用于惰性求值。

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

Answer 1

tl;dr 因为 infFib' 从不 return，它只会继续拨打电话。

我预计您在构建 infFib' 时的想法大致是这样的：

我想要一个无限列表。
我知道列表是如何开始的，以及列表应该如何增长。
我将编写一个函数来稍微增加列表，然后迭代它。
糟糕，Haskell 不进行迭代——它进行递归。好吧，我会写一个函数来稍微增加列表，然后用它递归。

不幸的是，按照您编写它的方式，您通过使用越来越长的列表调用自己来递归 - 但您永远不会 return （甚至部分）该列表给调用者！您只需不断构建一个越来越长的列表并对其调用 infFib'。

您应该做的是开始 return 列表中您有信心的部分，并增加您还没有信心的部分。例如：

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

此时，您可以在 ghci 中测试 infFib 是否确实有效并生成正确的答案。如果这符合您的需要，您可以到此为止。

但与可能的实现相比，此实现效率极低：在这里，infFib' 的参数列表越来越长，而它只真正关心最后两个元素。然后它必须遍历整个列表才能访问它关心的元素，这会浪费时间和内存。让我们通过只传递最后两个元素来解决这个问题。我们必须修复任何函数调用 infFib' —— 幸运的是，在这种情况下，因为它在本地作用域为 where 块，我们知道只有两个， infFib' 本身和区块的所有者，infFib。我们还必须内联 [] 的基本情况，因为在那种情况下我们还没有要传递的两个元素！

infFib = [0,1] ++ infFib' 0 1 where
        infFib' secondToLast last = [newPart] ++ infFib' last newPart
            where newPart = secondToLast + last

我会花一点时间思考如何清理它。我不确定它是否非常明显，但是让代码更清晰的一件事是将每次迭代中产生的元素 infFib' 向左移动两个——而不是产生第三个元素第一次调用时的斐波那契数列，在第一次调用时产生第一个元素。这将消除对额外 [0,1] ++ 和特殊 where 块的需要。所以：

infFib = infFib' 0 1 where
    infFib' old new = [old] ++ infFib' new (old+new)

最后一个：将 [x] ++ y 的定义展开为 x:y 是非常惯用的。这给了我们最终的定义

infFib = infFib' 0 1 where
    infFib' old new = old : infFib' new (old+new)

此时我会感到满意并继续我需要编写的下一个函数。

斐波那契函数的惰性评估

Lazy evaluation of Fibonacci function

recursion

haskell

fibonacci