10

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

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

为什么？！

呃......当使用优化编译时，即使禁用了单态限制，它也很快。

4

2 回答 2

11

通过给出明确的类型签名，您可以防止 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字典传递给fibin 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')

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

于 2012-06-21T22:34:24.460 回答
4

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

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

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

请注意，这些天让所有这些都被解雇是很狡猾的，而不是一概而论，等等。

于 2012-06-21T22:21:52.773 回答