NoMonomorphismRestriction有助于保持共享？

Question

当我偶然发现这种奇怪的行为时,我试图回答关于多态性与共享的另一个问题.

在GHCi中,当我明确定义一个多态常量时,它没有得到任何共享,这是可以理解的:

> let fib :: Num a => [a]; fib = 1 : 1 : zipWith (+) fib (tail fib)
> fib !! 30
1346269
(5.63 secs, 604992600 bytes)

另一方面,如果我试图通过省略类型签名并禁用单态限制来实现相同的目标,那么我的常量会突然被分享!

> :set -XNoMonomorphismRestriction
> let fib = 1 : 1 : zipWith (+) fib (tail fib)
> :t fib
fib :: Num a => [a]
> fib !! 50
20365011074
(0.00 secs, 2110136 bytes)

为什么？!

呃...当使用优化编译时,即使禁用单态限制也很快.

Answer 1

通过提供显式类型签名,可以防止GHC对您的代码做出某些假设.我将展示一个例子(取自这个问题):

foo (x:y:_) = x == y
foo [_]     = foo []
foo []      = False

根据GHCi的说法,这个功能的类型Eq a => [a] -> Bool正如您所期望的那样.但是,如果foo使用此签名声明,则会出现"模糊类型变量"错误.

此函数仅在没有类型签名的情况下工作的原因是因为类型检查在GHC中的工作原理.省略类型签名时,foo假定[a] -> Bool某些固定类型具有单一类型a.键入绑定组后,可以对类型进行概括.这就是你得到的地方forall a. ....

另一方面,当你声明一个多态类型签名时,你明确声明它foo是多态的(因此类型[]不必与第一个参数的类型匹配)和繁荣,你得到一个模糊的类型变量.

现在,知道这一点,让我们比较核心:

fib = 0:1:zipWith (+) fib (tail fib)
-----
fib :: forall a. Num a => [a]
[GblId, Arity=1]
fib =
  \ (@ a) ($dNum :: Num a) ->
    letrec {
      fib1 [Occ=LoopBreaker] :: [a]
      [LclId]
      fib1 =
        break<3>()
        : @ a
          (fromInteger @ a $dNum (__integer 0))
          (break<2>()
           : @ a
             (fromInteger @ a $dNum (__integer 1))
             (break<1>()
              zipWith
                @ a @ a @ a (+ @ a $dNum) fib1 (break<0>() tail @ a fib1))); } in
    fib1

而对于第二个:

fib :: Num a => [a]
fib = 0:1:zipWith (+) fib (tail fib)
-----
Rec {
fib [Occ=LoopBreaker] :: forall a. Num a => [a]
[GblId, Arity=1]
fib =
  \ (@ a) ($dNum :: Num a) ->
    break<3>()
    : @ a
      (fromInteger @ a $dNum (__integer 0))
      (break<2>()
       : @ a
         (fromInteger @ a $dNum (__integer 1))
         (break<1>()
          zipWith
            @ a
            @ a
            @ a
            (+ @ a $dNum)
            (fib @ a $dNum)
            (break<0>() tail @ a (fib @ a $dNum))))
end Rec }

使用显式类型签名,foo如上所述,GHC必须将其fib视为具有潜在多态性的递归值.我们可以将一些不同的Num字典传入fib,zipWith (+) fib ...并且此时我们必须抛弃大部分列表,因为不同Num意味着不同(+).当然,一旦你使用优化进行编译,GHC会注意到Num字典在"递归调用"期间永远不会改变并将其优化掉.

在上面的核心中,您可以看到GHC确实一次又一次地提供fib了一个Num字典(命名$dNum).

因为fib在完成整个绑定组的泛化之前没有类型签名被假定为单态,所以fib子部分被赋予与整体完全相同的类型fib.多亏了这个,fib看起来像:

{-# LANGUAGE ScopedTypeVariables #-}
fib :: forall a. Num a => [a]
fib = fib'
  where
    fib' :: [a]
    fib' = 0:1:zipWith (+) fib' (tail fib')

并且因为类型保持固定,您可以只使用在开始时给出的一个字典.