Fibonacci序列生成

Question

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

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

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

最初,因为Haskell的懒惰评估,env应该是fibs : [1,1,x],然后进行评估fibs,解释器评估在这种情况下的x哪个zipWith (+) fibs (tail fibs).在进行评估时zipWith,它fibs : [1,1,2,x]再次得益于Haskell的懒惰评估.并且fibs在这个时候env必然[1,1,2,x].但是,为了进行全面评估fibs,它会继续评估x,我们将回到之前的步骤.

它是否正确？

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

Answer 1

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

您缺少的关键因素是我们不必完全评估列表.绑定就像fibs = ...为表达式指定一个名称; 它不需要评估整个列表.Haskell只会根据需要运行的列表进行评估main.所以,例如,如果我们main是

main = print $ fibs !! 100

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

而且,即使我们正在评估整个事物(它将永远循环),我们也可以使用我们计算的部分.当你看到fibsghci 的值时,这就是正在发生的事情:它在计算每个元素时尽可能多地打印,并且不必等到整个列表准备就绪.

看到GHCi中的严格性

您可以ghci使用:sprint命令查看列表的评估量,该命令将打印Haskell数据结构,_以及尚未评估的部分(称为"thunks").您可以使用它来查看如何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示例(使用图表!)并讨论了如何将此方法用于一般记忆和动态编程.