斐波那契数列生成

Question

斐波那契数列生成

4

我正在编写一个斐波那契数列生成器，我试图理解Haskell中的以下代码：

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

我知道什么是zipWith，但我不确定程序如何执行以及为什么它确实生成所有斐波那契数。我试图使用函数式语言中的环境概念来理解为什么它不会终止：

最初，由于Haskell的惰性求值，中的绑定应该是fibs: [1,1,x]，然后要计算fibs，解释器首先需要计算x，这种情况下x是zipWith (+) fibs (tail fibs)。在计算zipWith时，它得到fibs：[1,1,2,x]，再次由于Haskell的惰性求值。此时，中的fibs绑定到[1,1,2,x]。但是，为了完全计算fibs，它继续计算x，我们回到了之前的步骤。

这样说是否正确？

此外，我注意到，当我在ghci中运行上面的程序时，它立即提示当前已计算的斐波那契序列，为什么？它不应该在完成所有计算后再打印结果吗？

- xwang

这里有一个我的回答，解释了这个计算是如何从“惰性”的角度工作的。其中一个副作用是，当你在GHCi中评估它时，它实际上被传递给print，它可以惰性地消耗列表，打印每个可用的元素。你定义的fibs列表实际上是无限的，你无法计算整个列表。 - bheklilr

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tikhon Jelvis · Accepted Answer

所以，你的大部分推理都是正确的。特别地，你正确地描述了每个新元素如何在旧元素的基础上进行评估。你也正确指出，要完全评估fibs需要重复你概述的步骤，并且实际上会永远循环。

你缺少的关键因素是我们不必完全评估列表。像fibs = ...这样的绑定只是将一个名称赋给表达式；它不需要评估整个列表。Haskell只会评估它运行main所需的列表部分。例如，如果我们的main是：

main = print $ fibs !! 100

Haskell只会计算前100个fibs元素（按照您所述的步骤），但不需要更多元素，也不会无限循环。此外，即使我们正在评估整个列表（将会无限循环），我们也可以在进行过程中使用我们已经计算出来的部分。这正是当您在ghci中看到fibs值时发生的情况：每个元素被计算时，它会尽可能地打印出来，并且不必等到整个列表准备好才能打印。

在ghci中，您可以使用:sprint命令查看列表已经评估了多少，它将打印一个带有未评估部分（称为“thunks”）的Haskell数据结构_。您可以使用此功能查看fibs的实际评估过程。

Prelude> let fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
Prelude> :sprint fibs
fibs = _
Prelude> print $ fibs !! 10
89
Prelude> :sprint fibs
fibs = _

糟糕，这不是我们预期的结果！事实上，这是一个缺乏单态性限制的问题所在。 fibs 获得了多态类型。

Prelude> :t fibs
fibs :: Num a => [a]

这意味着每次使用它时，它的行为类似于函数调用，而不是普通值。(在后台，GHC实现将实例化Num类型类作为将字典传递给fibs; 它的实现类似于一个NumDictionary a -> [a]函数。)

为了真正理解发生了什么，我们需要使fibs显式地变成单态。我们可以通过从启用该限制的模块加载它或给它一个明确的类型签名来实现这一点。让我们采取后者：

Prelude> let fibs :: [Integer]; fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
Prelude> :sprint fibs
fibs = _
Prelude> print $ fibs !! 10
89
Prelude> :sprint fibs
fibs = 1 : 1 : 2 : 3 : 5 : 8 : 13 : 21 : 34 : 55 : 89 : _

现在您可以看到哪些列表部分需要评估，哪些不需要，以获取第10个元素。您可以尝试其他列表或其他惰性数据结构，以深入了解后台发生的情况。

此外，您可以查看我的博客文章，了解这种惰性方式的更多细节。它详细介绍了fibs示例（附带图表！），并讨论如何将此方法用于一般记忆化和动态规划。