理解递归定义的列表(就 zipWith 而言的 fibs) [英] Understanding a recursively defined list (fibs in terms of zipWith)
问题描述
我正在学习 Haskell，并且遇到了以下代码:
I'm learning Haskell, and came across the following code:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
就其工作原理而言，我在解析时遇到了一些麻烦.它非常简洁，我知道不需要更多内容，但我想了解 Haskell 如何在我写作时设法填写"谎言:
which I'm having a bit of trouble parsing, in terms of how it works. It's very neat, I understand that nothing more is needed, but I'd like to understand how Haskell manages to "fill in" fibs when I write:
take 50 fibs
有什么帮助吗?
谢谢！
推荐答案
我将稍微解释一下它的内部工作原理.首先，您必须意识到 Haskell 使用一种称为 thunk 的东西作为其值.thunk 基本上是一个尚未计算的值——可以将其视为 0 个参数的函数.每当 Haskell 想要时，它都可以评估(或部分评估)thunk，将其转化为实际值.如果它只部分评估一个 thunk，那么结果值中将包含更多的 thunk.
I'll give a bit of an explanation of how it works internally. First, you must realise that Haskell uses a thing called a thunk for its values. A thunk is basically a value that has not yet been computed yet -- think of it as a function of 0 arguments. Whenever Haskell wants to, it can evaluate (or partly-evaluate) the thunk, turning it in to a real value. If it only partly evaluates a thunk, then the resulting value will have more thunks in it.
例如，考虑表达式:
(2 + 3, 4)
在普通语言中，这个值在内存中存储为 (5, 4)，但在 Haskell 中，它存储为 (.如果您要求该元组的第二个元素，它会告诉您4"，而不会将 2 和 3 相加.只有当您请求该元组的第一个元素时，它才会评估 thunk，并意识到它是 5.
In an ordinary language, this value would be stored in memory as (5, 4), but in Haskell, it is stored as (<thunk 2 + 3>, 4). If you ask for the second element of that tuple, it will tell you "4", without ever adding 2 and 3 together. Only if you ask for the first element of that tuple will it evaluate the thunk, and realise that it is 5.
对于 fibs，它有点复杂，因为它是递归的，但我们可以使用相同的想法.由于 fibs 没有参数，Haskell 将永久存储任何已发现的列表元素——这很重要.
With fibs, it's a bit more complicated, because it's recursive, but we can use the same idea. Because fibs takes no arguments, Haskell will permanently store any list elements that have been discovered -- that is important.
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
它有助于可视化 Haskell 当前对三个表达式的了解:fibs、tail fibs 和 zipWith (+) fibs (tail fibs).我们假设 Haskell 一开始就知道以下内容:
It helps to visualise Haskell's current knowledge of three expressions: fibs, tail fibs and zipWith (+) fibs (tail fibs). We shall assume Haskell starts out knowing the following:
fibs = 0 : 1 : <thunk1>
tail fibs = 1 : <thunk1>
zipWith (+) fibs (tail fibs) = <thunk1>
注意，第二行是第一行左移，第三行是前两行相加.
Note that the 2nd row is just the first one shifted left, and the 3rd row is the first two rows summed.
要求 take 2 fibs，你会得到 [0, 1].Haskell 无需进一步评估上述内容即可发现这一点.
Ask for take 2 fibs and you'll get [0, 1]. Haskell doesn't need to further evaluate the above to find this out.
请求 take 3 fibs 并且 Haskell 会得到 0 和 1，然后意识到它需要部分评估thunk.为了完全评估zipWith (+) fibs (tail fibs)，它需要对前两行求和——它不能完全做到这一点，但它可以开始 对前两行求和:
Ask for take 3 fibs and Haskell will get the 0 and 1, and then realise that it needs to partly evaluate the thunk. In order to fully evaluate zipWith (+) fibs (tail fibs), it needs to sum the first two rows -- it can't fully do that, but it can begin to sum the first two rows:
fibs = 0 : 1 : 1: <thunk2>
tail fibs = 1 : 1 : <thunk2>
zipWith (+) fibs (tail fibs) = 1 : <thunk2>
注意，我在第三行填写了1"，它也自动出现在第一行和第二行，因为所有三行都共享同一个 thunk(把它想象成一个被写入的指针)).因为它没有完成评估，它创建了一个新的 thunk，其中包含列表的 rest，如果需要的话.
Note that I filled in the "1" in the 3rd row, and it automatically appeared in the first and second rows as well, since all three rows are sharing the same thunk (think of it like a pointer that got written to). And because it didn't finish evaluating, it created a new thunk containing the rest of the list, should that ever be needed.
虽然不需要，因为 take 3 fibs 已经完成:[0, 1, 1].但是现在，假设您要求 take 50 fibs；Haskell 已经记住了 0、1 和 1.但它需要继续前进.所以它继续对前两行求和:
It isn't needed, though, because take 3 fibs is done: [0, 1, 1]. But now, say you ask for take 50 fibs; Haskell already remembers the 0, 1 and 1. But it needs to keep going. So it continues summing the first two rows:
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 对象保留，以防它需要更多.
And so on, until it has filled in 48 columns of the 3rd row, and thus has worked out the first 50 numbers. Haskell evaluates just as much as it needs, and leaves the infinite "rest" of the sequence as a thunk object in case it ever needs any more.
请注意，如果您随后要求 take 25 fibs，Haskell 将不会再次计算它——它只会从它已经计算过的列表中获取前 25 个数字.
Note that if you subsequently ask for take 25 fibs, Haskell will not evaluate it again -- it will just take the first 25 numbers from the list it has already calculated.
编辑:为每个 thunk 添加一个唯一编号以避免混淆.
Edit: Added a unique number to each thunk to avoid confusion.
这篇关于理解递归定义的列表(就 zipWith 而言的 fibs)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
