理解递归定义的列表（用 zipWith 表示的 fibs）

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 中，它存储为 (、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>

请注意，我在第三行中填写了“1”，它也自动出现在第一行和第二行中，因为所有三行都共享相同的 thunk（将其视为被写入的指针）。因为它没有完成评估，所以它创建了一个新的 thunk，其中包含列表的其余部分（如果需要的话）。

不过，这不是必需的，因为 take 3 fibs 已完成：[0, 1, 1]。但现在，假设您要求取 50 个小谎； 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 个数字。

编辑：为每个重击添加唯一的编号以避免混淆。

Answer 2

我不久前写过一篇关于此的文章。您可以在此处找到它。

正如我在那里提到的，请阅读 Paul Hudak 的书“The Haskell School of Expression”中的第 14.2 章，其中他使用斐波那契示例讨论了递归流。

注意：序列的尾部是没有第一项的序列。

|---+---+---+---+----+----+----+----+------------------------------------|
| 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)   |
|---+---+---+---+----+----+----+----+------------------------------------|

添加两列： add fibs (tail fibs) 得到 tail of tail of 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 只会根据需要计算足够的序列。

Answer 3

可以在此处找到一个非常相关的示例，尽管我还没有详细介绍它完全可能有一些帮助。

我不太确定实施细节，但我怀疑它们应该符合我下面的论点。

请对此持保留态度，这在实施上可能不准确，但只是作为一种理解帮助。

Haskell 不会评估任何东西，除非被迫，这被称为惰性评估，这本身就是一个美丽的概念。

因此，假设我们只被要求执行 take 3 fibs Haskell 将 fibs 列表存储为 0:1:another_list，因为我们被要求采取 3，我们不妨假设它存储为 fibs = 0:1:x:another_list 和 (tail fibs) = 1:x:another_list 和 0 : 1 : zipWith (+) fibs (tail fibs) 将是 0 : 1 : (0+1) : (1+x ) : (x+head another_list) ...

通过模式匹配，Haskell 知道 x = 0 + 1 所以引导我们到 0:1:1。

如果有人知道一些正确的实现细节，我会非常感兴趣。我可以理解，惰性求值技术可能相当复杂。

希望这有助于理解。

再次强制免责声明：请对此持保留态度，这在实施上可能不准确，但只是作为一种理解帮助。

Answer 4

我们来看看 zipWith 的定义
<代码>
zipWith f (x:xs) (y:ys) = fxy : zipWith xs ys

我们的谎言是：
<代码>
fibs = 0 : 1 : zipWith (+) fibs （尾部 fibs）

对于 take 3 fibs 替换 zipWith 和 xs = tail (x:xs) 的定义，我们得到
<代码>
0 : 1 : (0+1) : zipWith (+) (tail fibs) (tail (tail fibs))

对于 take 4 fibs 再次替换，我们得到
<代码>
0 : 1 : 1 : (1+1) : zipWith (+) (tail (tail fibs)) (tail (tail (tail fibs)))
等等

。