haskell - 斐波那契数列生成

Question

我正在编写一个斐波那契序列生成器，我试图理解 Haskell 中的以下代码
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

我明白了zipWith是，但我不完全知道程序是如何执行的，以及为什么它会生成所有的斐波那契数。我试图理解为什么它不会在函数式语言中使用环境概念终止，如下所示:

最初，由于 Haskell 的惰性求值，env 中的绑定(bind)应该是 fibs : [1,1,x] ，然后评估 fibs ，解释器评估 x这是zipWith (+) fibs (tail fibs)在这种情况下。在评估 zipWith 时, 它得到 fibs : [1,1,2,x] ，又是因为 Haskell 的懒惰评估。和fibs在 env绑定(bind)到 [1,1,2,x]此时。但是，要全面评估 fibs ，它继续评估 x我们回到前面的步骤。

它是否正确？

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

Answer 1

所以，你的大部分推理都是正确的。特别是，您正确描述了如何根据旧元素评估列表中的每个新元素。您完全评估 fibs 也是正确的。将需要重复您概述的步骤，并且实际上会永远循环。

您缺少的关键要素是 我们不必全面评估列表 .像 fibs = ... 这样的绑定(bind)只需为表达式分配一个名称；它不需要评估整个列表。 Haskell 将只评估它需要运行 main 的列表。 .因此，例如，如果我们的 main是

main = print $ fibs !! 100

Haskell 只会计算 fibs 的前 100 个元素(按照您概述的步骤)但不需要更多，也不会永远循环。

此外，即使我们正在评估整个事情(这将永远循环)，我们也可以使用我们计算的部分。当您看到 fibs 的值时，这正是正在发生的事情。在 ghci 中:它会尽可能多地打印每个正在计算的元素，而不必等到整个列表准备好。

在 GHCi 中看到严格性

您可以在 ghci 中查看列表的评估量。使用 :sprint命令将打印带有 _ 的 Haskell 数据结构对于尚未评估的部分(称为“thunk”)。您可以使用它来查看 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 个元素。您可以使用其他列表或其他惰性数据结构来很好地了解后台发生的事情。

另外，你可以看看 my blog post关于这种懒惰。它更详细地介绍了 fibs示例(带有图表!)并讨论如何使用这种方法进行一般内存和动态编程。