单态限制是什么?

86
我对Haskell编译器有时推断类型的能力感到困惑,这些类型不够多态化,例如在使用点-free定义时。看起来问题出在“单态约束”上,这在旧版本的编译器中默认开启。考虑以下Haskell程序:
{-# LANGUAGE MonomorphismRestriction #-}

import Data.List(sortBy)

plus = (+)
plus' x = (+ x)

sort = sortBy compare

main = do
  print $ plus' 1.0 2.0
  print $ plus 1.0 2.0
  print $ sort [3, 1, 2]

如果我使用ghc编译这个程序,就不会出现任何错误,并且可执行文件的输出结果为:
3.0
3.0
[1,2,3]

如果我更改主体部分为:main
main = do
  print $ plus' 1.0 2.0
  print $ plus (1 :: Int) 2
  print $ sort [3, 1, 2]

我没有编译时错误,输出结果如下:
3.0
3
[1,2,3]

正如预期的那样。但是,如果我尝试将其更改为:
main = do
  print $ plus' 1.0 2.0
  print $ plus (1 :: Int) 2
  print $ plus 1.0 2.0
  print $ sort [3, 1, 2]

我收到了一个类型错误:
test.hs:13:16:
    No instance for (Fractional Int) arising from the literal ‘1.0’
    In the first argument of ‘plus’, namely ‘1.0’
    In the second argument of ‘($)’, namely ‘plus 1.0 2.0’
    In a stmt of a 'do' block: print $ plus 1.0 2.0

尝试使用不同类型两次调用 sort 时,情况也是如此:
main = do
  print $ plus' 1.0 2.0
  print $ plus 1.0 2.0
  print $ sort [3, 1, 2]
  print $ sort "cba"

会产生以下错误:

test.hs:14:17:
    No instance for (Num Char) arising from the literal ‘3’
    In the expression: 3
    In the first argument of ‘sort’, namely ‘[3, 1, 2]’
    In the second argument of ‘($)’, namely ‘sort [3, 1, 2]’
  • 为什么ghc突然认为plus不是多态的,需要一个Int参数? 唯一提到Int的地方是在plus的应用程序中,当定义明显是多态时,这会有什么影响?
  • 为什么ghc突然认为sort需要一个Num Char实例?

此外,如果我尝试将函数定义放入它们自己的模块中,如:

{-# LANGUAGE MonomorphismRestriction #-}

module TestMono where

import Data.List(sortBy)

plus = (+)
plus' x = (+ x)

sort = sortBy compare

在编译时,我遇到了以下错误:

TestMono.hs:10:15:
    No instance for (Ord a0) arising from a use of ‘compare’
    The type variable ‘a0’ is ambiguous
    Relevant bindings include
      sort :: [a0] -> [a0] (bound at TestMono.hs:10:1)
    Note: there are several potential instances:
      instance Integral a => Ord (GHC.Real.Ratio a)
        -- Defined in ‘GHC.Real’
      instance Ord () -- Defined in ‘GHC.Classes’
      instance (Ord a, Ord b) => Ord (a, b) -- Defined in ‘GHC.Classes’
      ...plus 23 others
    In the first argument of ‘sortBy’, namely ‘compare’
    In the expression: sortBy compare
    In an equation for ‘sort’: sort = sortBy compare
  • 为什么ghc不能使用多态类型Ord a => [a] -> [a]来进行sort操作?
  • 为什么ghc对待plusplus'的方式不同?plus应该具有多态类型Num a => a -> a -> a,我真的看不出这与sort的类型有何不同,但只有sort会引发错误。

最后一件事:如果我注释掉sort的定义,文件就可以编译。然而,如果我尝试将其加载到ghci中并检查类型,则会得到:

*TestMono> :t plus
plus :: Integer -> Integer -> Integer
*TestMono> :t plus'
plus' :: Num a => a -> a -> a

plus为什么不是多态类型?


这是关于Haskell单态限制的规范问题,如在[元问题](https://meta.stackoverflow.com/questions/294053/can-we-provide-a-canonical-questionanswer-for-haskells-monomorphism-restrictio)中讨论。

为什么会突然发出公共服务公告呢?另外,我认为在你的答案中“关闭它”应该更加突出地推荐。 - dfeuer
2
@dfeuer 突然?元问题是在4个月前提出的。我在2周前发布了下面答案的草稿。我也在聊天中提到了这两个事实。对我来说,这不是“突然”。明天我会看看如何突出最重要的信息。 - Bakuriu
1
啊,我错过了元引用。 - dfeuer
1个回答

117
什么是单态限制?
Haskell维基百科所述的单态限制是:
“单态限制是Haskell类型推断中一个令人费解的规则。 如果你忘记提供类型签名,有时这个规则会使用“类型默认化”规则填充自由类型变量。”
这意味着,在某些情况下,如果您的类型不明确(即多态),编译器将选择将该类型实例化为不含歧义的内容。
如何修复它?
首先,您可以始终显式地提供类型签名,这将避免触发限制:
plus :: Num a => a -> a -> a
plus = (+)    -- Okay!

-- Runs as:
Prelude> plus 1.0 1
2.0

请注意,仅在变量上使用的普通类型签名才计入此目的,表达式类型签名不计。例如,编写以下代码仍会触发限制:
plus = (+) :: Num a => a -> a -> a

另外,如果你正在定义一个函数,你可以避免无点风格,例如写成:
plus x y = x + y

关闭它

可以简单地关闭限制,这样您就不必对代码进行任何修改来修复它。行为由两个扩展控制: MonomorphismRestriction 将启用它(这是默认设置),而 NoMonomorphismRestriction 将禁用它。

您可以将以下行放置在文件的最顶部:

{-# LANGUAGE NoMonomorphismRestriction #-}

如果你正在使用 GHCi,可以使用:set命令启用这个扩展:
Prelude> :set -XNoMonomorphismRestriction

您还可以通过命令行告诉 ghc 启用扩展:
ghc ... -XNoMonomorphismRestriction

注意:你应该真正优先选择第一种选项,而不是通过命令行选项来选择扩展。
请参考 GHC页面了解此及其他扩展的说明。
完整的解释
我将尝试在下面总结所有你需要知道的内容,以便理解单态限制是什么,为什么引入它以及它的行为方式。
一个例子
看下面这个简单的定义:
plus = (+)

你会认为能够将每个出现的 "+" 替换为 "plus"。特别是因为 "(+) :: Num a => a -> a -> a",你还期望有 "plus :: Num a => a -> a -> a"。
不幸的是,事实并非如此。例如,如果我们在 GHCi 中尝试以下操作:
Prelude> let plus = (+)
Prelude> plus 1.0 1

我们得到以下输出:
<interactive>:4:6:
    No instance for (Fractional Integer) arising from the literal ‘1.0’
    In the first argument of ‘plus’, namely ‘1.0’
    In the expression: plus 1.0 1
    In an equation for ‘it’: it = plus 1.0 1

您可能需要在新的GHCi版本中添加:set -XMonomorphismRestriction。实际上,我们可以看到plus的类型并不是我们期望的类型。
Prelude> :t plus
plus :: Integer -> Integer -> Integer

发生的事情是编译器看到了plus的类型为Num a => a -> a -> a,一个多态类型。此外,正如我稍后会解释的规则所述,以上定义符合默认化类型变量a的规则。默认值是Integer,可以看到。
请注意,如果您尝试使用ghc编译上面的代码,不会收到任何错误。这是由于ghci如何处理(并且必须处理)交互式定义造成的。基本上,在考虑以下内容之前,ghci中输入的每个语句都必须被完全类型检查;换句话说,它就像每个语句都在单独的模块中一样。稍后我会解释为什么这很重要。
其他示例:
考虑以下定义:
f1 x = show x

f2 = \x -> show x

f3 :: (Show a) => a -> String
f3 = \x -> show x

f4 = show

f5 :: (Show a) => a -> String
f5 = show

我们希望所有这些函数的行为方式和类型都相同,即show的类型应为:Show a => a -> String
然而,在编译上述定义时,我们会得到以下错误:
test.hs:3:12:
    No instance for (Show a1) arising from a use of ‘show’
    The type variable ‘a1’ is ambiguous
    Relevant bindings include
      x :: a1 (bound at blah.hs:3:7)
      f2 :: a1 -> String (bound at blah.hs:3:1)
    Note: there are several potential instances:
      instance Show Double -- Defined in ‘GHC.Float’
      instance Show Float -- Defined in ‘GHC.Float’
      instance (Integral a, Show a) => Show (GHC.Real.Ratio a)
        -- Defined in ‘GHC.Real’
      ...plus 24 others
    In the expression: show x
    In the expression: \ x -> show x
    In an equation for ‘f2’: f2 = \ x -> show x

test.hs:8:6:
    No instance for (Show a0) arising from a use of ‘show’
    The type variable ‘a0’ is ambiguous
    Relevant bindings include f4 :: a0 -> String (bound at blah.hs:8:1)
    Note: there are several potential instances:
      instance Show Double -- Defined in ‘GHC.Float’
      instance Show Float -- Defined in ‘GHC.Float’
      instance (Integral a, Show a) => Show (GHC.Real.Ratio a)
        -- Defined in ‘GHC.Real’
      ...plus 24 others
    In the expression: show
    In an equation for ‘f4’: f4 = show

所以f2f4不能编译。此外,在尝试在GHCi中定义这些函数时,我们没有得到任何错误,但是f2f4的类型是() -> String

单态化限制是使f2f4需要单态化类型的原因,而ghcghci之间不同的行为是由于不同的默认规则造成的。

它什么时候发生?

在Haskell中,根据报告定义,有两种不同类型的绑定。函数绑定和模式绑定。函数绑定只是定义函数的定义:

f x = x + 1

请注意,它们的语法是:
<identifier> arg1 arg2 ... argn = expr

取模保护和where声明。但它们并不重要。 < p >其中必须至少有一个参数。

< p >模式绑定是以下形式的声明:

<pattern> = expr

再次提醒,要使用模运算符进行保护。
请注意,变量也是一种模式,因此绑定如下:
plus = (+)

这是一个模式绑定。它将模式plus(一个变量)绑定到表达式(+)

当一个模式绑定仅包含一个变量名时,它被称为简单模式绑定。

单态限制适用于简单模式绑定!

好吧,严格来说:

声明组是一组最小的相互依赖的绑定。

report第4.5.1节。

然后(见report第4.5.5节):

给定的声明组仅当以下条件成立时才是无限制的:
1. 组中的每个变量都由函数绑定(例如 `f x = x`)或简单模式绑定(例如 `plus = (+)`;见第 4.4.3.2 节)绑定。 2. 对于由简单模式绑定绑定的每个变量,都提供了显式类型签名(例如 `plus :: Num a => a -> a -> a; plus = (+)`)。
因此,受限制的声明组是一个组,其中有非简单模式绑定(例如 `(x:xs) = f something` 或 `(f, g) = ((+), (-))`),或者有一些没有类型签名的简单模式绑定(如 `plus = (+)`)。
单态化限制影响受限制的声明组。
大多数情况下,您不定义相互递归的函数,因此声明组仅成为一个绑定。
它是做什么的?
单态限制由报告第4.5.5节中的两个规则描述。
第一条规则:
通常Hindley-Milner对多态的限制是只有在环境中没有自由出现的类型变量才能被泛化。此外,在受限制的声明组的泛化步骤中,受约束的类型变量不能被泛化。(回想一下,如果必须属于某个类型类,则类型变量是受约束的;请参见第4.5.2节。)
这里突出显示的部分是单态限制引入的内容。 它表明,如果类型是多态的(即包含某些类型变量),并且该类型变量受到约束(即它有一个类约束:例如,类型Num a => a -> a -> a是多态的,因为它包含a,并且也受到约束,因为a上有Num约束。),那么它就不能被泛化。
简单来说,不泛化意味着函数plus使用可能会改变其类型。
如果你有以下定义:
plus = (+)

x :: Integer
x = plus 1 2

y :: Double
y = plus 1.0 2

如果这样做,你会得到一个类型错误。因为当编译器看到在声明变量x时,plus被调用在Integer上时,它将统一类型变量aInteger,因此plus的类型变成了:
Integer -> Integer -> Integer

但是,当它检查y的定义时,它会发现plus被应用于一个Double参数,而类型不匹配。

请注意,您仍然可以使用plus而不会出错:

plus = (+)
x = plus 1.0 2

在这种情况下,首先推断出plus的类型为Num a => a -> a -> a,但是在定义x时,其中1.0需要一个Fractional约束,这将使其变为Fractional a => a -> a -> a

解释

报告中说:

Rule 1 is required for two reasons, both of which are fairly subtle.

  • Rule 1 prevents computations from being unexpectedly repeated. For example, genericLength is a standard function (in library Data.List) whose type is given by

      genericLength :: Num a => [b] -> a
    

    Now consider the following expression:

      let len = genericLength xs
      in (len, len)
    

    It looks as if len should be computed only once, but without Rule 1 it might be computed twice, once at each of two different overloadings. If the programmer does actually wish the computation to be repeated, an explicit type signature may be added:

      let len :: Num a => a
          len = genericLength xs
      in (len, len)
    
这一点,我相信从维基百科的例子更加清晰。 考虑以下函数:
f xs = (len, len)
  where
    len = genericLength xs

如果`len`是多态的,那么`f`的类型将是什么:
f :: Num a, Num b => [c] -> (a, b)

所以元组 (len, len) 的两个元素实际上可以是不同的值!但这意味着必须重复使用 genericLength 进行计算以获得两个不同的值。
这里的理由是:代码包含一个函数调用,但如果不引入这个规则,就可能产生两个隐藏的函数调用,这是不直观的。
有了单态限制,f 的类型变成了:
f :: Num a => [b] -> (a, a)

通过这种方式,就不需要多次执行计算。
  • Rule 1 prevents ambiguity. For example, consider the declaration group

     [(n,s)] = reads t
    

    Recall that reads is a standard function whose type is given by the signature

     reads :: (Read a) => String -> [(a,String)]
    

    Without Rule 1, n would be assigned the type ∀ a. Read a ⇒ a and s the type ∀ a. Read a ⇒ String. The latter is an invalid type, because it is inherently ambiguous. It is not possible to determine at what overloading to use s, nor can this be solved by adding a type signature for s. Hence, when non-simple pattern bindings are used (Section 4.4.3.2 ), the types inferred are always monomorphic in their constrained type variables, irrespective of whether a type signature is provided. In this case, both n and s are monomorphic in a.

好的,我认为这个例子是不言自明的。有时候不遵循规则会导致类型模糊的情况。
如果按照上面建议禁用扩展,当尝试编译以上声明时,您将会得到一个类型错误。但这并不是真正的问题:您已经知道在使用`read`时必须以某种方式告诉编译器应该尝试解析哪种类型...
第二条规则
  1. 当对整个模块进行类型推断后,仍存在任何单态类型变量,则被视为模糊的,并使用默认规则(第4.3.4节)解析为特定类型。
这意味着,如果您有通常的定义:
plus = (+)

这将具有类型 Num a => a -> a -> a,其中a是由上述规则1确定的单态类型变量。一旦整个模块被推断出来,编译器将根据默认规则选择一个类型来替换a
最终结果是:plus :: Integer -> Integer -> Integer
请注意,这是在整个模块被推断之后完成的。
这意味着如果您有以下声明:
plus = (+)

x = plus 1.0 2.0

在一个模块内,在进行类型默认之前,plus 的类型将是:Fractional a => a -> a -> a(参见规则1,了解为什么会这样)。 此时,根据默认规则,a 将被替换为 Double,因此我们将有 plus :: Double -> Double -> Doublex :: Double

默认化

如前所述,存在一些默认化规则,详见报告的第4.3.4节,类型推断器可以采用这些规则,并将多态类型替换为单态类型。这发生在类型存在歧义的情况下。

例如,在以下表达式中:

let x = read "<something>" in show x

这里的表达不太明确,因为showread的类型是:
show :: Show a => a -> String
read :: Read a => String -> a

所以 x 的类型为 Read a => a。但是这个约束对很多类型都成立:例如 IntDouble 或者 ()。该选择哪种类型呢?没有任何方法可以告诉我们。
在这种情况下,我们可以通过添加类型签名来消除歧义,告诉编译器我们想要的类型。
let x = read "<something>" :: Int in show x

现在的问题是:由于Haskell使用Num类型类来处理数字,因此存在许多数值表达式包含歧义的情况。
考虑以下例子:
show 1

结果应该是什么?
与之前一样,1 的类型为 Num a => a,有许多类型的数字可以使用。选择哪一个呢?
几乎每次使用数字都会出现编译器错误,这并不是一件好事,因此引入了默认规则。可以使用 default 声明来控制规则。通过指定 default (T1, T2, T3),我们可以更改推断器默认不同类型的方式。
如果模糊的类型变量 v 满足以下条件,则可默认:
  • v 仅出现在类别 C v 的约束中(即如果它出现在 Monad (m v) 中,则不可默认)。
  • 这些类别中至少有一个是 NumNum 的子类。
  • 所有这些类别都在 Prelude 或标准库中定义。
可默认的类型变量将会被替换为在 default 列表中,首个同时实现了所有不明确变量类的类型。

默认 default 声明是 default (Integer, Double)

例如:

plus = (+)
minus = (-)

x = plus 1.0 1
y = minus 2 1

推断出的类型将是:
plus :: Fractional a => a -> a -> a
minus :: Num a => a -> a -> a

根据默认规则,它变成了:
plus :: Double -> Double -> Double
minus :: Integer -> Integer -> Integer

请注意,这就解释了为什么在问题示例中只有sort定义会引发错误。类型Ord a => [a] -> [a]不能默认化,因为Ord不是一个数值类。
扩展默认规则
请注意,GHCi带有扩展型默认规则(或这里适用于GHC8),可以在文件中启用使用ExtendedDefaultRules扩展。
可默认化的类型变量不必仅仅出现在所有类都是标准类的约束中,并且至少有一个类属于EqOrdShowNum及其子类之一。
此外,默认的“default”声明为“default ((), Integer, Double)”。 这可能会产生奇怪的结果。以问题中的示例为例:
Prelude> :set -XMonomorphismRestriction
Prelude> import Data.List(sortBy)
Prelude Data.List> let sort = sortBy compare
Prelude Data.List> :t sort
sort :: [()] -> [()]

在ghci中,我们不会得到类型错误,但Ord a的约束会导致默认值为(),这几乎没有用处。

有用的链接

有许多关于单态化限制的资源和讨论。

以下是我认为有用的链接,可能会帮助您理解或深入了解此主题:


我还没有读完这个答案,因为我注意到在这个答案中声称的几个 GHCi 行被认为是错误的,但当我尝试它们时并没有出错,所以我认为它可能有点过时了。例如,在 GHCi 中输入 let plus = (+) 然后输入 plus 1.0 1 就可以正常工作,打印出 2.0。这是因为在这五年左右的时间里发生了一些变化吗? - Enlico
1
@Enlico 我相信从 GHCi 7.8.1 开始,默认情况下启用了 NoMonomorphismRestriction 扩展(参见:https://typeclasses.com/timeline#ghc-7.8.1),但对于编译代码来说并非如此。实际上,我的答案提到了这一点:*在较新的 GHCi 版本中,您可能需要使用 :set -XMonomorphismRestriction。* - Bakuriu
好的,谢谢。我没有看到那个注释和我观察到的东西之间的联系,抱歉。 - Enlico

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接