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

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

首先回忆一下以下是等价的：

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

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

fibs = 0 : 1 : ...

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

现在考虑一下 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 将评估第一步）

Answer 2

最终添加了整个列表。在 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         └-----│---│-┘ | │
                                                      │   └───┘ │
                                                      └─────────┘

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

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

Elegant way in Haskell to output Fibonacci numbers using zipWith

haskell

fibonacci

zipwith