协同递归和协同数据

Question

我想逐步了解一下Haskell中的以下功能

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

我知道"fibs“通常是”懒惰“的，所以下一项将被计算为”随需应变“，但是我不确定"tail”函数如何在无限列表上工作。

因此，说明它如何与一些中间数据一起工作将会有所帮助。

Answer 1

一开始，求值是这样的：

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

如果我们用它的评估替换fibs，它看起来是这样的：

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

其中?表示未计算的thunk。让我们评估一下fibs的下一个元素

fibs = 0 : 1 : zipWith (+) (0 : 1 : ?) (1 : ?) ==>
fibs = 0 : 1 : 1 : zipWith (+) (1 : ?) (?)

使用zipWith的每个参数列表的第一个元素。现在，当我们评估它时，我们也知道，下一个thunk的值是什么，我们可以填写它。这允许我们评估下一个单元格，依此类推：

fibs = 0 : 1 : 1 : zipWith (+) (1 : ?) (?) ==>
fibs = 0 : 1 : 1 : zipWith (+) (1 : 1 : ?) (1 : ?) ==>
fibs = 0 : 1 : 1 : 2 : zipWith (+) (1 : ?) (?) ==>
fibs = 0 : 1 : 1 : 2 : zipWith (+) (1 : 2 : ?) (2 : ?) ==>
fibs = 0 : 1 : 1 : 2 : 3 : zipWith (+) (2 : ?) (?) ==>
...

Answer 2

无限列表上的tail非常简单:如果需要，生成第一个参数，然后丢弃它。

所以

fibs       =  0 : 1 : fibs'
tail fibs  =      1 : fibs'

和

tail fibs         =  1 : 1 : fibs''
tail (tail fibs)  =      1 : fibs''

和

tail (tail fibs)         =  1 : 2 : fibs'''
tail (tail (tail fibs))  =      2 : fibs'''

等。

Answer 3

从后端开始：

• tail返回不带头部的列表内容，例如[2,3]
• zipWith --> [11,22]
• fibs对两个列表的内容进行成对应用，例如tail [1,2,3] --> zipWith (+) [1,2] [10,20]定义为一个从0和1开始的列表，然后zipWith操作的结果为

下面是一个模式，它解释了zipWith中发生的事情

       v-searching the third value of fibs
fibs: [0,1,...]
tail: [1,.....]
--------------
sum:  [1,.....]

now fibs is sum together with the leading 0 and 1:

         v-searching the fourth value of fibs
fibs: [0,1,1,.....]
tail: [1,1,.......]
-------------------
sum:  [1,2,.......] 

now fibs is sum together with the leading 0 and 1:

           v-searching the fifth value of fibs
fibs: [0,1,1,2,.....] 
tail: [1,1,2,.......] 
----------------------
sum:  [1,2,3,.......] 

now fibs is sum together with the leading 0 and 1:

             v-searching the sixth value of fibs
fibs: [0,1,1,2,3,.....] 
tail: [1,1,2,3,.......] 
------------------------
sum:  [1,2,3,5,.......]

所以你可以看到，如果你采取“一步一步”的行动，你可以派生出整个列表，这是可能的，因为Haskell的懒惰行为。