理解递归定义的列表(就zipWith而言)

Question

我正在学习Haskell,并且遇到了以下代码:

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

就其工作方式而言,我在解析方面遇到了一些麻烦.它非常整洁,我知道不需要更多内容,但我想了解Haskell在写作时如何设法"填写"文件:

take 50 fibs

有帮助吗？

谢谢!

Answer 1

我将给出一些内部工作原理的解释.首先,你必须意识到Haskell使用一个叫做thunk的东西作为它的值.thunk基本上是一个尚未计算的值 - 将其视为0参数的函数.每当Haskell想要时,它都可以评估(或部分评估)thunk,将其转换为实际值.如果它仅部分评估thunk,则结果值将包含更多的thunk.

例如,考虑表达式:

(2 + 3, 4)

在普通语言中,此值将作为存储在内存中(5, 4),但在Haskell中,它将存储为(<thunk 2 + 3>, 4).如果你要求该元组的第二个元素,它会告诉你"4",而不是一起添加2和3.只有当你要求该元组的第一个元素时,它才会评估thunk,并意识到它是5.

对于fibs,它有点复杂,因为它是递归的,但我们可以使用相同的想法.因为fibs没有参数,Haskell将永久存储已发现的任何列表元素 - 这很重要.

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

它有助于可视化三个表达式的Haskell的现有知识: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>

请注意,我填写了第3行中的"1",它也自动出现在第一行和第二行中,因为所有三行都共享相同的thunk(想象它就像一个写入的指针).并且由于它没有完成评估,它创建了一个包含列表其余部分的新thunk ,如果需要的话.

但是,不需要它,因为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>

依此类推,直到它填满了第3行的48列,从而得出了前50个数字.Haskell根据需要进行评估,并将序列的无限"休息"留作thunk对象,以防它再次需要.

请注意,如果您随后要求take 25 fibs,Haskell将不再对其进行评估 - 它将从已经计算的列表中获取前25个数字.

编辑:为每个thunk添加一个唯一的编号,以避免混淆.

Answer 2

我前一段时间写了一篇文章.你可以在这里找到它.

正如我在那里提到的,请阅读Paul Hudak的书"The Haskell School of Expression"中的第14.2章,其中他使用Fibonacci示例谈论递归流.

注意:序列的尾部是没有第一个项目的序列.

|---+---+---+---+----+----+----+----+------------------------------------|
| 1 | 1 | 2 | 3 |  5 |  8 | 13 | 21 | Fibonacci sequence (fibs)          |
|---+---+---+---+----+----+----+----+------------------------------------|
| 1 | 2 | 3 | 5 |  8 | 13 | 21 | 34 | tail of Fib sequence (tail fibs)   |
|---+---+---+---+----+----+----+----+------------------------------------|

添加两列:添加fibs(tail fibs)以获得fib序列尾部的尾部

|---+---+---+---+----+----+----+----+------------------------------------|
| 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | tail of tail of Fibonacci sequence |
|---+---+---+---+----+----+----+----+------------------------------------|

add fibs(tail fibs)可以写成zipWith(+)fibs(tail fibs)

现在,我们需要通过从前2个斐波纳契数开始来获得完整的斐波纳契序列来完成这一代.

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

注意:此递归定义不适用于执行急切评估的典型语言.它适用于haskell,因为它进行了懒惰的评估.所以,如果你要求前4个斐波纳契数,需要4个纤维,haskell只根据需要计算足够的序列.