在Haskell中使用zipWith输出斐波那契数的优雅方式

Question

我在Haskell中看到了斐波那契数的这种实现方式，但我仍在试图弄清楚为什么它可以正常工作。因此，很显然，可以使用zipWith函数以非常紧凑的方式编写斐波那契数。该实现如下所示

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

为了更好地了解此处发生的情况，我查看了zipWith函数的文档。此函数使用给定的函数（a-> b-> c）将两个列表[a]，[b]一起添加。在我们的例子中，该功能是一个简单的添加。如果两个列表[a]和[b]的长度不同（在我们的例子中，列表[b]总是比列表[a]短一个元素），则zipWith只是从两个列表的开头开始并将它们相加。如果到达一个列表的末尾，则无论已到达另一个列表的末尾，它都会停止。

在递归的第一步中，使用[0,1]和tail [0,1] = [1]调用zipWith。这导致另一个1 => [0，1，1]。在递归的第二步中，使用[0,1,1]和[1,1]调用zipWith，导致[0 + 1,1 + 1] = [1,2]。因此，对我来说，很明显，递归创建了正确的斐波那契数字，但是我不完全理解为什么仅将zipWith步骤之后的最后一个数字添加到结果中，而不是整个列表中。也许有人可以向我解释。那会很有帮助。非常感谢你。

Answer 1

在整个名单最终加入。在Haskell中，您不会为变量分配值。您声明一个变量，并且由于这些变量是不可变的，因此无法更改变量的值。这份名单是这样不 [0, 1]，它是[0, 1, …]与…东西是在尚未评估的那一刻。

因此，最初的列表如下所示：

    ?????????????????????????????????????
    ?           ??????????????????????? ?
    ?           ?                     | ?
?---?---?   ?---?---?   ?-----------? | ?
| ? | ??????| ? | ??????|  zipWith  | | ?
?-?-?---?   ?-?-?---?   ?-----------? | ?
  ?           ?         |(+)| ? | ? | | ?
  0           1         ?-----?---?-? | ?
                              ?   ????? ?
                              ???????????

如果您以后决定评估列表的下一项，zipWith将计算其所引用列表的首位总和，因此[0,1,…]和[1,…]，即为1。因此，它将发出1，并递归到两个列表的末尾：

                ?????????????????????????????????????
                ?           ??????????????????????? ?
                ?           ?                     | ?
?---?---?   ?---?---?   ?---?---?   ?-----------? | ?
| ? | ??????| ? | ??????| ? | ??????|  zipWith  | | ?
?-?-?---?   ?-?-?---?   ?-?-?---?   ?-----------? | ?
  ?           ?           ?         |(+)| ? | ? | | ?
  0           1           1         ?-----?---?-? | ?
                                          ?   ????? ?
                                          ???????????

所以现在的清单是[0,1,1,…]。然后，如果我们强制系统评估下一项，它将再次汇总列表的首部，所以[1,1,…]和[1,…]，即2：

                            ?????????????????????????????????????
                            ?           ??????????????????????? ?
                            ?           ?                     | ?
?---?---?   ?---?---?   ?---?---?   ?---?---?   ?-----------? | ?
| ? | ??????| ? | ??????| ? | ??????| ? | ??????|  zipWith  | | ?
?-?-?---?   ?-?-?---?   ?-?-?---?   ?-?-?---?   ?-----------? | ?
  ?           ?           ?           ?         |(+)| ? | ? | | ?
  0           1           1           2         ?-----?---?-? | ?
                                                      ?   ????? ?
                                                      ???????????

等等。因此，该列表是一个无限列表，但是尾部的计算是延迟的。