list - 了解递归定义的列表（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 中，它存储为(<thunk 2 + 3>, 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 无需进一步评估上述内容即可找出答案。

Ask fortake 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]. 但是现在，说你要求take 50 fibs; 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 个数字。

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

Answer 2

不久前我写了一篇关于这个的文章。你可以在这里找到它。

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

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

|---+---+---+---+----+----+----+----+------------- ----------------------|
| 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 斐波那契数列 (fibs) |
|---+---+---+---+----+----+----+----+------------- ----------------------|
| 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | Fib 序列的尾部 (tail fibs) |
|---+---+---+---+----+----+----+----+------------- ----------------------|

添加两列：add fibs(tail fibs)得到fib序列的tail of tail

|---+---+---+---+----+----+----+----+------------- ----------------------|
| 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 斐波那契数列尾尾 |
|---+---+---+---+----+----+----+----+------------- ----------------------|

add fibs (tail fibs) 可以写成 zipWith (+) fibs (tail fibs)

现在，我们需要做的就是从前 2 个斐波那契数开始，得到完整的斐波那契数列。

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

注意：此递归定义不适用于进行急切评估的典型语言。它在haskell中工作，因为它进行惰性评估。因此，如果您要求前 4 个斐波那契数，取 4 个 fibs，haskell 只会根据需要计算足够的序列。

Answer 3

可以在此处找到一个非常相关的示例，尽管我还没有完全了解它，但它可能会有所帮助。

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

请加一点盐，这在实施上可能不准确，但只是作为理解帮助。

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

所以让我们假设我们只被要求做一个Haskelltake 3 fibs将fibs列表存储为0:1:another_listtake 3fibs = 0:1:x:another_list(tail fibs) = 1:x:another_list0 : 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) = f x y : zipWith xs ys

我们的谎言是： fibs = 0 : 1 : zipWith (+) fibs (tail 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)))

等等。