haskell - 奇怪的 GHCi 惰性评估

Question

我在 ghci 中为偶数和奇数定义了两个相互递归列表，如下所示:

> let evens = 0:map (+1) odds; odds = map (+1) evens

然后我使用 :sp 咨询 thunk

> :sp evens
evens = _
> :sp odds
odds = _
> take 5 evens
[0,2,4,6,8]
> :sp evens
evens = 0 : 2 : 4 : 6 : 8 : _
:sp odds
odds = _

请注意，尽管 evens 已计算到第 5 个元素，但 odds thunk 并未计算。我能想到一个直观的解释。 odds 必须显式调用才能进行评估:

> take 5 odds
[1,3,5,7,9]
>:sp odds
odds = 1 : 3 : 5 : 7 : 9 : _

但是，现在当我这样做时:

> take 10 evens
[0,2,4,6,8,10,12,14,16,18]
> :sp evens
evens = 0 : 2 : 4 : 6 : 8 : 10 : 12 : 14 : 16 : 18 : _
> :sp odds
odds = 1 : 3 : 5 : 7 : 9 : 11 : 13 : 15 : 17 : _

请注意，每当评估evens时，现在如何评估odds thunk？为什么odds第一次不进行评估，而在第二次和所有后续评估中进行评估？发生了什么？

Answer 1

这与 GHC 编译相互递归绑定(bind)的方式有关(并且绑定(bind)是否具有显式类型签名存在差异)。

让我们编写以下简单的程序，该程序暴露了相同的问题，但消除了对整数重载或单态限制可能发挥的作用的所有怀疑:

module MutRec where

ft = False : map not tf
tf = map not ft

将其加载到 GHCi(我使用的是 7.6.3)中，结果是:

*MutRec> take 5 ft
[False,False,False,False,False]
*MutRec> :sp ft
ft = False : False : False : False : False : _
*MutRec> :sp tf
tf = _

让我们看看这个模块的核心代码

$ ghc -O0 MutRec -fforce-recomp -ddump-simpl -dsuppress-all
[1 of 1] Compiling MutRec           ( MutRec.hs, MutRec.o )

==================== Tidy Core ====================
Result size of Tidy Core = {terms: 28, types: 42, coercions: 0}

Rec {
ft1_rkA
ft1_rkA = : False a_rkC

tf1_rkB
tf1_rkB = map not ft1_rkA

a_rkC
a_rkC = map not tf1_rkB
end Rec }

ds_rkD
ds_rkD = (ft1_rkA, tf1_rkB)

ft
ft = case ds_rkD of _ { (ft2_Xkp, tf2_Xkr) -> ft2_Xkp }

tf
tf = case ds_rkD of _ { (ft2_Xkq, tf2_Xks) -> tf2_Xks }

这说明了一切。相互递归的定义最终出现在 Rec block 中，直接相互引用。但随后 GHC 正在构建一对 ds_rkD 并从该对中重新提取组件。这是一个额外的间接。它解释了为什么在 GHCi 中部分评估 ft 后，tf 的顶部仍然会显示为 thunk，即使下面已经进行了评估。事实上，我们可以验证仅对 tf 进行最少的评估就足以揭示这一点:

*MutRec> take 5 ft
[False,False,False,False,False]
*MutRec> :sp ft
ft = False : False : False : False : False : _
*MutRec> :sp tf
tf = _
Prelude MutRec> seq tf ()
()
Prelude MutRec> :sp tf
tf = True : True : True : True : _

如果我们向 ft 和 tf 添加显式类型签名或启用优化，则不会发生元组构造:

$ ghc -O MutRec -fforce-recomp -ddump-simpl -dsuppress-all
[1 of 1] Compiling MutRec           ( MutRec.hs, MutRec.o )

==================== Tidy Core ====================
Result size of Tidy Core = {terms: 12, types: 11, coercions: 0}

Rec {
ft1
ft1 = map not tf

ft
ft = : False ft1

tf
tf = map not ft
end Rec }

现在 GHCi 的行为会更加自然。

<小时/>

编辑

我查看了 GHC 来源，试图找出差异的原因行为。这似乎是多态绑定(bind)的类型推断工作方式的副作用。

如果绑定(bind)是多态的但没有类型签名，那么它的递归使用是单态的。这是 Hindley-Milner 中 GHC 也实现的限制。如果你想多态递归，您需要额外的类型签名。

为了在核心语言中忠实地对此进行建模，脱糖者制作了一个单态副本每个未注释的递归函数。这个单态版本用于递归调用，通用版本用于外部调用。即使是很小的东西你也能看到这一点诸如 rep 之类的函数(它是 repeat 的重新实现)。脱糖核心

rep x = x : rep x

是

rep
rep =
  \ (@ a_aeM) ->
    letrec {
      rep_aeJ
      rep_aeJ =
        \ (x_aeH :: a_aeM) -> : @ a_aeM x_aeH (rep_aeJ x_aeH); } in
    rep_aeJ

外部 rep 是多态的，因此开头的类型抽象 \(@ a_aeM) -> 。内部 rep_aeJ 是单态的，用于递归调用。

如果向 rep 添加显式类型注释

rep :: a -> [a]
rep x = x : rep x

那么递归调用就是多态版本，生成的Core就变成了更简单:

Rec {
rep
rep = \ (@ a_b) (x_aeH :: a_b) -> : @ a_b x_aeH (rep @ a_b x_aeH)
end Rec }

您可以看到类型参数 @ a_b 如何在开头被选取并重新应用在每个递归调用中rep。

我们看到的相互递归绑定(bind)的元组构造只是一个这一原则的概括。您构建了相互的内部单态版本递归函数，然后将它们概括为元组，并提取多态元组的版本。

所有这一切的发生与绑定(bind)是否实际上是多态无关。它们递归就足够了。我认为GHC的这种行为完全是正确且正常，特别是因为优化可以解决性能影响。