在Haskell中对无限列表中的术语进行惰性求值

Question

我很好奇无限列表的运行时性能,如下所示:

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

这将创建一个无限的斐波那契序列表.

我的问题是,如果我做以下事情:

takeWhile (<5) fibs

fibs评估列表中每个术语的次数是多少？似乎自从takeWhile检查列表中每个项目的谓词函数后,fibs列表将多次评估每个项目.前两个学期是免费的.当takeWhile想要评估 (<5)第3个元素时,我们将获得:

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个元素.此外,如果谓词in takeWhile很大,则表明函数正在做更多需要的工作,因为它多次评估列表中的每个前面的元素.我的分析在这里是正确的还是Haskell做了一些缓存来防止多次评估？

Answer 1

这是一种自引用的惰性数据结构,其中结构的"后面"部分按名称引用较早的部分.

最初,该结构只是一个计算,未评估的指针返回自身.展开时,会在结构中创建值.稍后对已经计算过的结构部分的引用能够找到已经存在的值等待它们.无需重新评估这些碎片,也无需额外的工作!

内存中的结构只是一个未经评估的指针.一旦我们查看第一个值,它看起来像这样:

> 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 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>

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

¹这当然不是语言语义严格要求的,但在实践中总是如此.