我对Haskell的懒惰评估感到困惑

Question

我关注Haskell懒惰评估的效率.考虑以下代码

main = print $ x + x
   where x = head [1..]

在这里,由于懒惰,x首先保持表达head [1..]而不是结果1,但是当我调用时x + x,表达式head [1..]会被执行两次吗？

我在haskell.org上找到了以下描述

另一方面,懒惰评估意味着仅在需要其结果时评估表达式(注意从"缩减"到"评估"的转变).因此,当评估引擎看到一个表达式时,它会构建一个thunk数据结构,其中包含评估表达式所需的任何值,以及指向表达式本身的指针.当实际需要结果时,评估引擎调用表达式,然后将thunk替换为结果以供将来参考.

那么这是否意味着,在x + x调用第一个时x,head [1..]执行并x重新分配1,第二个x只是调用它的引用？

我明白了吗？

Answer 1

这是关于特定Haskell实现的问题,而不是关于Haskell本身的问题,因为该语言对事物的评估方式没有特别的保证.

但是在GHC(以及大多数其他实现中,据我所知):是的,当评估thunks时,它们会被内部结果替换,因此对同一thunk的其他引用会从第一次对其进行评估的工作中受益.

需要注意的是,对于哪些表达式最终实现为对同一个thunk的引用,并没有真正的保证.一般情况下,只要结果相同,编译器就可以对它喜欢的代码进行任何转换.当然,在编译器中实现代码转换的原因通常是尝试使代码更快,因此希望不会以使其变得更糟的方式重写事物,但它永远不会是完美的.

但实际上,你通常会非常安全地假设每当你给表达式命名(如where x = head [1..])时,那么所有对该名称的使用(在绑定范围内)都将引用一个thunk.

Answer 2

起初,x只是一个thunk.你可以看到如下:

? Prelude> let x = head [1..]
? Prelude> :sprint x
x = _

这里_表示x尚未评估.它的纯粹定义被记录下来.

然后,你可以x + x通过实现这x是一个指向这个thunk的指针来理解如何构造:这两个x指向同一个thunk.一旦被评估,另一个是,因为它是相同的thunk.

你可以看到ghc-vis:

? Prelude> :vis
? Prelude> :view x
? Prelude> :view x + x

应该告诉你一些事情:

在这里你可以看到x + xthunk实际上指向thunk两次x.

现在,如果您x通过打印它进行评估,例如:

? Prelude> print x

你会得到:

你可以在这里看到xthunk不再是thunk:它是值1.