理解递归定义的列表（使用zipWith定义斐波那契数列）

Question

理解递归定义的列表（使用zipWith定义斐波那契数列）

listhaskelllazy-evaluationfibonaccilazy-sequences

73

我正在学习Haskell，并遇到了以下代码：

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

我有些难以理解的代码，不太清楚它是如何工作的。我很清楚这段代码非常巧妙，只是我希望能够理解当我写下这样的代码时，Haskell是如何“填充”fibs的。

take 50 fibs

任何帮助？

谢谢！

- Frank

4个回答

23

我之前写过一篇文章，涉及到这个问题。你可以在这里找到它。

正如我之前提到的，在Paul Hudak的书《表达式的Haskell学派》中的第14.2章，他用斐波那契数列的例子讲解了递归流。

注意：序列的尾部是不含第一个元素的序列。

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

将这两列相加：add fibs (tail fibs) 得到 斐波那契数列的头两位之后的序列

|---+---+---+---+----+----+----+----+------------------------------------|
| 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 斐波那契数列的头两位之后的序列   |
|---+---+---+---+----+----+----+----+------------------------------------|

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

现在，我们只需要通过从前两个斐波那契数开始生成，就可以得到完整的斐波那契数列。

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

注意：这个递归定义在典型的急切求值语言中不起作用。它在Haskell中起作用，因为它进行了惰性求值。因此，如果你要求前4个斐波那契数，take 4 fibs，Haskell只会计算所需的部分序列。

- Babu Srinivasan

3

可以在这里找到一个非常相关的示例运行，点击此处，尽管我还没有完全浏览它，但可能会有所帮助。

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

请将其视为一种理解辅助工具，但也要保持审慎，因为它的实现可能不准确。

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

因此，让我们假设我们只被要求执行take 3 fibs。Haskell将fibs列表存储为0:1:another_list，因为我们被要求take 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。

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

希望这有助于理解。

强制性声明：请再次将此视为参考，实现可能不准确，仅作为理解辅助。

- Afroz

1

让我们来看一下zipWith的定义：


zipWith f (x:xs) (y:ys) = f x y : zipWith xs ys

我们的fibs是：


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

依此类推。

- ArthurVard

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mgiuca · Accepted Answer

我来简单解释一下它的内部运作方式。首先，你必须意识到Haskell使用一种叫做thunk的东西来表示其值。Thunk基本上是一个尚未计算的值--可以将其视为没有参数的函数。每当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 不需要进一步评估上面的内容来找到这个结果。

如果请求 take 3 fibs，Haskell 将得到 0 和 1，并且意识到它需要部分地评估这个惰性求值。为了完全求值 zipWith (+) fibs (tail fibs)，它需要对前两行求和 -- 它不能完全求和，但它可以开始求和前两行：

fibs                         = 0 : 1 : 1: <thunk2>
tail fibs                    = 1 : 1 : <thunk2>
zipWith (+) fibs (tail fibs) = 1 : <thunk2>

请注意，我在第三行填入了“1”，它自动出现在第一和第二行中，因为这三行都共享同一个thunk（将其视为被写入的指针）。由于它没有完成计算，它创建了一个新的thunk，其中包含列表的其余部分rest，如果需要的话。
但实际上并不需要，因为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中，以避免混淆。