在Haskell的无限列表中对术语进行懒惰的评估

我很好奇如下的无限列表的运行时性能：

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

这将创build斐波纳契序列的无限列表。

我的问题是，如果我做到以下几点：

 takeWhile (<5) fibs 

fibs评估列表中的每个术语多less次？ 看起来，因为takeWhile检查列表中每个项目的谓词函数， fibs列表将会多次评估每个项目。 前两项是免费的。 当takeWhile想在第三个元素上评估(<5)时，我们会得到：

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

现在，一旦想要在第四个元素上评估(<5) ： fibs的recursion性质将再次构build列表如下：

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

当我们想要评估第四个元素的值时，似乎需要再次计算第三个元素。 而且，如果takeWhile的谓词很大，则表示该函数正在做更多的工作，因为它正在多次评估列表中的每个前面的元素。 这里我的分析是正确的还是Haskell做一些caching，以防止在这里多次评估？

Answer 1

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

最初，这个结构只是一个没有评估指针的计算。 展开后，值将在结构中创build。 稍后对结构已经计算的部分的引用能够find已经在那里等待的值。 没有必要重新评估这些作品，也没有额外的工作要做！

内存中的结构开始只是一个未评估的指针。 一旦我们看到第一个值，它看起来像这样：

 > take 2 fibs 

（指向一个cons单元的指针，指向'1'，尾部持有第二个'1'，以及指向一个函数的指针，该函数将引用保存到fibs，以及fibs的尾部。

多一步的评估扩大了结构，并沿着以下的方向滑动参考：

所以我们开始展开结构，每次产生一个新的未评估的尾部，这是一个闭包，将参考返回到最后一步的第一和第二个元素。 这个过程可以继续无限的:)

而且，因为我们是通过名字来指代以前的价值，所以GHC愉快地将它们留在我们的记忆中，所以每个项目只被评估一次。

Answer 2

插图：

 module TraceFibs where import Debug.Trace fibs :: [Integer] fibs = 0 : 1 : zipWith tadd fibs (tail fibs) where tadd xy = let s = x+y in trace ("Adding " ++ show x ++ " and " ++ show y ++ "to obtain " ++ show s) s 

哪个产生

 *TraceFibs> fibs !! 5 Adding 0 and 1 to obtain 1 Adding 1 and 1 to obtain 2 Adding 1 and 2 to obtain 3 Adding 2 and 3 to obtain 5 5 *TraceFibs> fibs !! 5 5 *TraceFibs> fibs !! 6 Adding 3 and 5 to obtain 8 8 *TraceFibs> fibs !! 16 Adding 5 and 8 to obtain 13 Adding 8 and 13 to obtain 21 Adding 13 and 21 to obtain 34 Adding 21 and 34 to obtain 55 Adding 34 and 55 to obtain 89 Adding 55 and 89 to obtain 144 Adding 89 and 144 to obtain 233 Adding 144 and 233 to obtain 377 Adding 233 and 377 to obtain 610 Adding 377 and 610 to obtain 987 987 *TraceFibs> 

Answer 3

当在Haskell中评估某些东西时，只要它被引用了相同的名称¹ ，就会保持评估。

在下面的代码中，列表l只被评估一次（这可能是显而易见的）：

 let l = [1..10] print l print l -- None of the elements of the list are recomputed 

即使部分评估，部分仍然评估：

 let l = [1..10] print $ take 5 l -- Evaluates l to [1, 2, 3, 4, 5, _] print l -- 1 to 5 is already evaluated; only evaluates 6..10 

---

在你的例子中，当fibs列表的一个元素被评估，它保持评估。 由于zipWith的参数引用了实际的fibs列表，这意味着当计算列表中的下一个元素时，压缩expression式将使用已经部分计算的fibs列表。 这意味着没有元素被评估两次。

¹这当然不是语言语义学所严格要求的，但实际上情况总是如此。

Answer 4

想想这样。 variablesfib是一个指向懒值的指针。 （你可以把下面的一个懒惰的值看作是一个数据结构，比如（不是真正的语法） Lazy a = IORef (Unevaluated (IO a) | Evaluated a) ;也就是说，它始于未评估的thunk;然后当它被评估“改变”到记住值的东西）。因为recursionexpression式使用variablesfib ，所以它们有一个指向相同的lazy值的指针（它们“共享”数据结构）。 第一次有人评价fib ，它运行thunk得到的价值和价值被记住。 而且因为recursionexpression式指向相同的懒惰数据结构，所以当他们评估它时，他们将会看到评估值。 当他们遍历懒惰的“无限列表”时，内存中只有一个“部分列表” zipWith将有两个指向“列表”的指针，这些指针只是指向同一个“列表”的前一个成员的指针，因为它是以指向同一个列表的指针开始的。

请注意，这不是真正的“记忆”。 这只是参考相同variables的结果。 通常没有“记忆”function结果（以下将是低效的）：

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