1

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

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

To understand better what is happening here I looked at the documentation of the zipWith function. This function adds two lists [a], [b] together using the given function (a -> b -> c). In our case the function is a simple addition. If the two lists [a] and [b] have different length (in our case list [b] is always one element shorted than list [a]) zipWith simply starts at the beginning of both lists and adds them. If the end of one list is reached it just stops no matter if the end of the other list is already reached.

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

4

2 回答 2

5

最终会添加整个列表。在 Haskell 中，您不会为变量赋值。您声明了一个变量，并且您不能更改变量的值，因为它们是不可变的。因此，该列表不是 [0, 1]，而是[0, 1, …]，其中包含…当时尚未评估的内容。

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

    ┌───────────────────────────────────┐
    │           ┌─────────────────────┐ │
    ▼           ▼                     | │
┌---┼---┐   ┌---┼---┐   ┌-----------┐ | │
| ∙ | ∙────▶| ∙ | ∙────▶|  zipWith  | | │
└-│-┴---┘   └-│-┴---┘   ├-----------┤ | │
  ▼           ▼         |(+)| ∙ | ∙ | | │
  0           1         └-----│---│-┘ | │
                              │   └───┘ │
                              └─────────┘

如果您稍后决定评估列表的下一项，zipWith将计算它所引用的列表的头部的总和，所以[0,1,…]和[1,…]，这是一个。因此它将发出1，并在两个列表的尾部递归：

                ┌───────────────────────────────────┐
                │           ┌─────────────────────┐ │
                ▼           ▼                     | │
┌---┬---┐   ┌---┼---┐   ┌---┼---┐   ┌-----------┐ | │
| ∙ | ∙────▶| ∙ | ∙────▶| ∙ | ∙────▶|  zipWith  | | │
└-│-┴---┘   └-│-┴---┘   └-│-┴---┘   ├-----------┤ | │
  ▼           ▼           ▼         |(+)| ∙ | ∙ | | │
  0           1           1         └-----│---│-┘ | │
                                          │   └───┘ │
                                          └─────────┘

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

                            ┌───────────────────────────────────┐
                            │           ┌─────────────────────┐ │
                            ▼           ▼                     | │
┌---┬---┐   ┌---┬---┐   ┌---┼---┐   ┌---┼---┐   ┌-----------┐ | │
| ∙ | ∙────▶| ∙ | ∙────▶| ∙ | ∙────▶| ∙ | ∙────▶|  zipWith  | | │
└-│-┴---┘   └-│-┴---┘   └-│-┴---┘   └-│-┴---┘   ├-----------┤ | │
  ▼           ▼           ▼           ▼         |(+)| ∙ | ∙ | | │
  0           1           1           2         └-----│---│-┘ | │
                                                      │   └───┘ │
                                                      └─────────┘

等等。因此，该列表是一个无限列表，但尾部是惰性求值的。

于 2019-09-03T10:33:07.550 回答
3

列表没有变化的长度。长度总是无穷大，我们只是不知道大多数元素。

首先记住以下是等价的：

[1,2,3]
1:2:3:[]

在这种情况下，我们将写入...尚未评估的列表尾部。所以最初我们有

fibs = 0 : 1 : ...

并检查...（看看它是否是[]或看起来像的东西n : ...），我们评估一些调用zipWith

现在考虑zipWith将要做什么：

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

但请注意，当然，这些评估步骤仅在迭代 fibs 的元素时发生（例如，评估take 5 fibs将评估第一步）

于 2019-09-03T10:28:45.857 回答