斐波纳契序列的生成
我正在编写一个斐波那契序列生成器，并试图理解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的懒惰评估。 env fibs绑定到[1,1,2,x] 。 但是，为了充分评估fibs ，它继续评估x ，然后回到前面的步骤。
它是否正确？
另外，我注意到当我用ghci运行上面的程序时，它立即提示它当前计算的斐波那契数列，为什么？ 不应该在完成所有计算后打印结果吗？
所以，你的大部分推理是正确的。 特别是，您正确地描述了列表中每个新元素是如何评估旧元素的。 您完全评估fibs需要重复您列出的步骤并且实际上会永远循环，这也是正确的。
您错过的关键因素是我们不必完全评估列表 。 像fibs = ...的绑定只是给表达式分配一个名称; 它不需要评估整个列表。 Haskell只会评估列表，因为它需要运行main 。 举例来说，如果我们的main是
main = print $ fibs !! 100
Haskell只会计算fibs的前100个元素（按照您列出的步骤），但不会再需要这些元素，并且不会永远循环。
而且，即使我们正在评估整个事情（将永远循环），我们也可以使用我们计算的部分。 当你看到ghci中的fibs的值时，就会发生这种情况：每个元素都被计算出来并且不需要等待整个列表准备好就可以打印出来。
看到GHCi的严格性
你可以看到有多少列表在ghci使用:sprint命令进行评估， :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示例（使用图表！）并讨论如何将这种方法用于一般的memoization和动态编程。
上一篇: Fibonacci sequence generation
下一篇: how to calculate time complexity in big O notation of this algorithm