haskell - Haskell 中无限列表中项的惰性求值

Question

我很好奇像这样的无限列表的运行时性能下面这个:

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

这将创建斐波那契数列的无限列表。

我的问题是，如果我执行以下操作:

takeWhile (<5) fibs

fibs 有多少次评估列表中的每个术语？它似乎从takeWhile开始检查中每个项目的谓词函数列表，fibs列表将多次评估每个术语。这前 2 学期免费。当takeWhile想要评估 (<5)在第三个元素上，我们将得到:

1 : 1 : zipWith (+) [(1, 1), (1)] => 1 : 1 : 3

现在，一次takeWhile想评价(<5)第四个元素:fibs 的递归性质将再次构建列表，就像以下:

1 : 1 : zipWith (+) [(1, 2), (2, 3)] => 1 : 1 : 3 : 5

当我们想要评估第四个元素的值。此外，如果takeWhile 中的谓词很大，这表明函数是做更多需要的工作，因为它正在评估前面的每一个列表中的元素多次出现。我在这里的分析是正确的还是Haskell 进行一些缓存以防止此处进行多次求值？

Answer 1

这是一个自引用的惰性数据结构，其中结构的“后面”部分通过名称引用前面的部分。

最初，该结构只是一个带有返回自身的未计算指针的计算。随着它的展开，值(value)在结构中被创造出来。稍后对结构中已计算部分的引用能够找到已经在那里等待它们的值。无需重新评估各个部分，也无需做额外的工作!

内存中的结构一开始只是一个未计算的指针。一旦我们查看第一个值，它看起来像这样:

> take 2 fibs

(指向 cons 单元的指针，指向“1”，尾部保存第二个“1”，以及指向保存对 fib 的引用的函数的指针，以及 fib 的尾部。

再评估一个步骤会扩展结构，并滑动引用文献:

因此我们展开结构，每次都会产生一个新的未评估的尾部，这是一个保留对最后一步的第一个和第二个元素的引用的闭包。这个过程可以无限继续:)

因为我们通过名称引用先前的值，GHC 很乐意为我们将它们保留在内存中，因此每个项目仅评估一次。