42

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

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)第 4 个元素：递归性质fibs将再次构造列表，如下所示：

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

当我们想要评估第 4 个元素的值时，似乎需要再次计算第 3 个元素。此外，如果谓词 intakeWhile很大，则表明该函数正在执行更多所需的工作，因为它多次评估列表中的每个前面的元素。我的分析是正确的还是 Haskell 做了一些缓存来防止这里的多次评估？

4

4 回答 4

81

这是一个自引用的惰性数据结构，其中结构的“较晚”部分按名称引用较早的部分。

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

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

> take 2 fibs

在此处输入图像描述

（指向 cons 单元格的指针，指向 '1'，尾部保存第二个 '1'，以及指向函数的指针，该函数保存对 fibs 的引用和 fibs 的尾部。

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

在此处输入图像描述

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

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

于 2012-06-10T22:26:00.587 回答
31

插图：

module TraceFibs where

import Debug.Trace

fibs :: [Integer]
fibs = 0 : 1 : zipWith tadd fibs (tail fibs)
  where
    tadd x y = 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>
于 2012-06-10T21:38:37.063 回答
19

当在 Haskell 中评估某些东西时，只要它被同名1引用，它就会保持评估状态。

在下面的代码中，列表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列表的参数，这意味着压缩表达式将在计算fibs列表中的下一个元素时使用已经部分计算的列表。这意味着没有元素被评估两次。

1这当然不是语言语义严格要求的，但在实践中总是如此。

于 2012-06-10T21:31:33.267 回答
4

这样想吧。该变量fib是指向惰性值的指针。（您可以将下面的惰性值视为一种数据结构，例如（不是真正的语法）Lazy a = IORef (Unevaluated (IO a) | Evaluated a)；即，它一开始是用 thunk 未评估的；然后当它被评估时，它“改变”为记住该值的东西。）因为递归表达式使用变量fib，它们有一个指向相同惰性值的指针（它们“共享”数据结构）。有人第一次评估fib时，它会运行 thunk 来获取值，并且会记住该值。而且因为递归表达式指向相同的惰性数据结构，所以当他们评估它时，他们已经看到了评估的值。当他们遍历惰性“无限列表”时，内存中只会有一个“部分列表”；zipWith将有两个指向“列表”的指针，它们只是指向同一“列表”的先前成员的指针，因为它以指向同一列表的指针开始。

请注意，这并不是真正的“记忆”；这只是引用相同变量的结果。函数结果一般没有“记忆”（以下将是低效的）：

fibs () = 0 : 1 : zipWith tadd (fibs ()) (tail (fibs ()))
于 2012-06-10T22:39:31.627 回答