理解递归定义的列表（以zipWith为单位的fibs） [英] Understanding a recursively defined list (fibs in terms of zipWith)

问题描述

  fibs = 0：1：zipWith（+） fibs（tail fibs）
  

我在解析时遇到了一些麻烦，作品。它非常整洁，我明白没有什么需要，但我想了解Haskell在写代码时如何填充fibs：

  take 50 fibs 
  

有什么帮助？

谢谢！

解决方案

我会给出一些内部解释。首先，你必须认识到，Haskell使用一种称为 thunk 的东西来表示它的值。 thunk基本上是一个尚未计算的值 - 将其视为0个参数的函数。每当Haskell想要的时候，它都可以评估（或部分评估）thunk，并将其转化为实际价值。如果它只是部分地评估一个thunk，那么结果值将会有更多thunk。

例如，考虑下面的表达式： （2 + 3，4）

$ b $ $ $ $ $ $
$ b

在普通语言中，这个值将作为（5，4）存储在内存中，但在Haskell中，它存储为（< thunk 2 + 3> ;, 4）< / code> ;.如果你询问该元组的第二个元素，它会告诉你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> 
  

请注意，第二行是第一个向左移动，第三行是前两个

要求取2 fibs ，你会得到 [0， 1] 。 Haskell不需要进一步评估上面的内容就可以发现它。

要求以3个fibs 和Haskell会得到0和1，然后意识到它需要部分评估thunk。为了充分评估 zipWith（+）fibs（tail fibs），它需要对前两行进行求和 - 它不能完全做到这一点，但它可以 begin 来总结前两行：

  fibs = 0：1：1：< thunk2> 
 tail fibs = 1：1：< thunk2> 
 zipWith（+）fibs（tail fibs）= 1：< thunk2> 
  

请注意，我在第三行填入了1，并且它自动出现在第一行和第二行，因为所有三行都共享相同的thunk（想象它像写入的指针）。因为它没有完成评估，所以它创建了一个包含列表的 rest 的新的thunk，如果需要的话。

它但是，因为取3 fibs 完成： [0,1,1] 。但是现在，假设你要求取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> 
  

等等，直到它填满了第三行的48列为止，前50个号码。 Haskell对它的需求进行评估，并将剩下的序列作为一个thunk对象留出，以备需要时再使用。

请注意，如果你随后要求取25 fibs ，Haskell不会再评估它 - 它只会从已经计算的列表中取出前25个数字。

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

I'm learning Haskell, and came across the following code:

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

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

Any help?

Thanks!

解决方案

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.

For example, consider the expression:

(2 + 3, 4)

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.

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)

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.

Ask for take 2 fibs and you'll get [0, 1]. Haskell doesn't need to further evaluate the above to find this out.

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>

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.

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>

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.

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.

Edit: Added a unique number to each thunk to avoid confusion.

这篇关于理解递归定义的列表（以zipWith为单位的fibs）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！