NoMonomorphismRestriction有助于保持共享



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

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

为什么?!

呸。。。当使用优化进行编译时,即使禁用单态限制,它的速度也很快。

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

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

根据GHCi的说法,此功能的类型是 Eq a => [a] -> Bool ,正如您所期望的那样。但是,如果使用此签名声明foo,则会收到"不明确的类型变量"错误。

此函数仅在没有类型签名的情况下工作的原因是因为类型检查在 GHC 中的工作方式。省略类型签名时,假定foo具有某些固定类型a的单类型[a] -> Bool。键入完绑定组后,将通用化类型。这就是你得到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')

由于类型保持固定,因此您可以只使用开始时给出的一个字典。

在这里,

您在两种情况下都使用具有相同类型参数的fib,并且ghc足够聪明,可以看到这一点并执行共享。

现在,如果您使用了可以用不同类型的参数调用的函数,并且默认导致其中一个与另一个非常不同,那么缺乏单态限制会咬你。

考虑在没有单态限制的两个上下文中x = 2 + 2多态地使用术语,在一个上下文中你show (div x 2),在另一个上下文中使用show (x / 2),在一个设置中,你得到IntegralShow约束,这导致你默认为Integer,在另一个设置中,你得到一个Fractional和一个Show约束,默认你Double, 因此,计算结果不会共享,因为您正在使用应用于两种不同类型的多态术语。打开单态限制后,它会尝试为积分和分数设置默认值一次,但失败。

请注意,这些天让这一切变得不一概而论等的技巧。

最新更新