理解一个recursion定义的列表（以zipWith为单位的fibs）
我正在学习Haskell，并遇到以下代码：
fibs = 0 : 1 : zipWith (+) fibs (tail fibs) 这在parsing方面有点麻烦，就其工作原理而言。 这是非常整洁，我明白，没有什么是必要的，但我想了解，当我写的时候，Haskell如何设法“填补”fibs：
take 50 fibs
任何帮助？
谢谢！
我会解释一下它在内部是如何工作的。 首先，你必须认识到，Haskell使用一个叫做thunk的东西来表示它的值。 一个thunk基本上是一个还没有被计算出来的值 – 把它想象成0个参数的函数。 每当Haskell想要，它可以评估（或部分评估）thunk，把它变成一个真正的价值。 如果它只是部分地评估一个thunk，那么结果值将会有更多的thunk。
例如，考虑下面的expression式：
(2 + 3, 4)
在普通的语言中，这个值将被存储在内存中(5, 4) 5,4 (5, 4) ，但是在Haskell中，它被存储为(<thunk 2 + 3>, 4) 。 如果你要求这个元组的第二个元素，它会告诉你“4”，而不会把2和3加在一起。 只有当你询问这个元组的第一个元素时，它才会评估这个thunk，并意识到它是5。
随着fibs，它有点复杂，因为它是recursion的，但我们可以使用相同的想法。 由于fibs不需要任何参数，Haskell将永久存储任何已经被发现的列表元素 – 这很重要。
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
它有助于将Haskell当前对三个expression式的知识可视化： fibs ， tail fibs和zipWith (+) fibs (tail fibs) 。 我们将假设Haskell开始知道以下内容：
fibs = 0 : 1 : <thunk1> tail fibs = 1 : <thunk1> zipWith (+) fibs (tail fibs) = <thunk1>
请注意，第二行是刚刚向左移动的第一行，第三行是前两行的总和。
要求take 2 fibs ，你会得到[0, 1] 。 Haskell不需要进一步评估上面的发现。
要求take 3 fibs和Haskell将得到0和1，然后意识到它需要部分评估 thunk。 为了充分评估zipWith (+) fibs (tail fibs) ，它需要总结前两行 – 它不能完全做到这一点，但它可以开始总结前两行：
fibs = 0 : 1 : 1: <thunk2> tail fibs = 1 : 1 : <thunk2> zipWith (+) fibs (tail fibs) = 1 : <thunk2>
请注意，我在第三行中填入了“1”，并且它自动出现在第一行和第二行，因为所有三行都共享相同的thunk（想象它像写入的指针）。 而且因为它没有完成评估，它创build了一个包含列表的其余部分的新的thunk，如果需要的话。
但是这并不是必须的，因为take 3 fibs ： [0, 1, 1] take 3 fibs [0, 1, 1] 。 但是现在说，你要求take 50 fibs ， Haskell已经记得0,1和1.但是它需要继续。 所以它继续总结前两行：
fibs = 0 : 1 : 1 : 2 : <thunk3> tail fibs = 1 : 1 : 2 : <thunk3> zipWith (+) fibs (tail fibs) = 1 : 2 : <thunk3>
…
fibs = 0 : 1 : 1 : 2 : 3 : <thunk4> tail fibs = 1 : 1 : 2 : 3 : <thunk4> zipWith (+) fibs (tail fibs) = 1 : 2 : 3 : <thunk4>
依此类推，直到填满第三排48栏为止，计算出前50位数字。 Haskell可以根据需要进行评估，并将剩余的“剩余”作为一个thunk对象，以防需要更多时间。
请注意，如果您随后要求提取take 25 fibs ，那么Haskell将不会再评估它 – 它只会从已经计算的列表中获得前25个数字。
编辑 ：为每个thunk添加一个唯一的编号，以避免混淆。
我早就写了一篇文章。 你可以在这里find它。
正如我在那里提到的，请阅读Paul Hudak的书“The Haskell School of Expression”中的第14.2章，他使用Fibonacci的例子谈论recursionstream。
注：序列的尾部是没有第一个项目的序列。
| --- + --- + --- + --- + ---- + ---- + ---- + ---- + ------------- ----------------------- | | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 斐波那契数列（fibs）| | --- + --- + --- + --- + ---- + ---- + ---- + ---- + ------------- ----------------------- | | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | Fib序列（tail fibs）的尾部| | --- + --- + --- + --- + ---- + ---- + ---- + ---- + ------------- ----------------------- |
添加两列： 添加fibs（tail fibs）以获得fib序列尾部的尾部
| --- + --- + --- + --- + ---- + ---- + ---- + ---- + ------------- ----------------------- | | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 斐波那契数列的尾部尾部 | --- + --- + --- + --- + ---- + ---- + ---- + ---- + ------------- ----------------------- |
添加fibs（tail fibs）可以写成zipWith（+）fibs（tail fibs）
现在，我们需要做的第一个2斐波那契数字，以获得完整的斐波纳契序列。
1：1：zipWith（+）fibs（tail fibs）
注意：这个recursion定义不适用于一个渴望评估的典型语言。 它在哈斯克尔工作，因为它懒惰的评价。 所以，如果你问前4个斐波那契数， 取4个fibs ，haskell只计算足够的顺序。
一个非常相关的例子可以在这里find，虽然我还没有完全了解它可能有一些帮助。
我不太确定实施细节，但我怀疑他们应该在我的论点下面。
请拿一点盐，这可能在实践上不准确，但作为一种理解的援助。
Haskell不会评估任何事情，除非被迫，那就是所谓的懒惰评估，这本身就是一个美丽的概念。
所以我们假设我们只被要求做take 3 fibs Haskell把fibs列表存储为0:1:another_list ，因为我们被要求take 3我们可以假设它存储为fibs = 0:1:x:another_list和(tail fibs) = 1:x:another_list和0 : 1 : zipWith (+) fibs (tail fibs)将会是0 : 1 : (0+1) : (1+x) : (x+head another_list) ...
通过模式匹配Haskell知道x = 0 + 1所以导致我们到0:1:1 。
如果有人知道一些正确的实施细节，我会非常感兴趣。 我可以理解，懒惰评估技术虽然可能相当复杂。
希望这有助于理解。
强制性的免责声明：请拿一小撮盐，这可能实际上不准确，但作为一种理解的援助。
让我们来看看zipWith zipWith f (x:xs) (y:ys) = fxy : zipWith xs ys定义zipWith f (x:xs) (y:ys) = fxy : zipWith xs ys
我们的fibs是： fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
take 3 fibsreplacezipWith和xs = tail (x:xs)的定义，我们得到0 : 1 : (0+1) : zipWith (+) (tail fibs) (tail (tail fibs))
0 : 1 : 1 : (1+1) : zipWith (+) (tail (tail fibs)) (tail (tail (tail fibs)))
等等。
