haskell - 什么是单态性限制？

Question

我对haskell编译器有时会推断出类型较少的类型感到困惑
比我预期的多态，例如在使用无点定义时。

似乎问题出在“单态限制”上，默认情况下，“单态限制”处于启用状态
较旧版本的编译器。

考虑以下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对plus和plus'的对待不同？ 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中单态限制的规范问题
如 the meta question中所述。

Answer 1

什么是单态性限制？
Haskell Wiki声明的monomorphism restriction为:

a counter-intuitive rule in Haskell type inference.If you forget to provide a type signature, sometimes this rule will fillthe free type variables with specific types using "type defaulting" rules.

这意味着在某些情况下，如果您的类型不明确(即多态)
编译器将选择将该类型实例化为不明确的内容。
我如何解决它？
首先，您始终可以明确提供类型签名，这将
避免触发限制:

plus :: Num a => a -> a -> a
plus = (+)    -- Okay!

-- Runs as:
Prelude> plus 1.0 1
2.0

另外，如果您要定义一个函数，则可以避免 point-free style，
例如:

plus x y = x + y

关掉它
可以简单地关闭限制，这样您就不必做
修改您的代码中的任何内容。该行为由两个扩展控制: MonomorphismRestriction将启用它(这是默认设置)，同时 NoMonomorphismRestriction将禁用它。
您可以将以下行放在文件的最上方:

{-# LANGUAGE NoMonomorphismRestriction #-}

如果您正在使用GHCi，则可以使用 :set命令启用扩展:

Prelude> :set -XNoMonomorphismRestriction

您还可以从命令行告诉 ghc启用扩展:

ghc ... -XNoMonomorphismRestriction

注意:您真的应该首选第一个选项，而不是通过命令行选项选择扩展名。
有关此扩展名和其他扩展名的说明，请引用 GHC's page。
完整的解释
我将尝试在下面总结您需要了解的所有内容，以了解
单态限制是什么，为什么引入它以及如何表现。
一个例子
采取以下简单定义:

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

因此 f2和 f4无法编译。此外，当尝试定义这些功能时
在GHCi中，我们没有收到任何错误，但是 f2和 f4的类型是 () -> String!
单态性限制是 f2和 f4需要单态性的原因
类型，并且 ghc和 ghci之间的行为不同是由于不同
默认规则。
什么时候发生？
在 report定义的Haskell中，有两种不同的 bindings类型。
函数绑定(bind)和模式绑定(bind)。函数绑定(bind)无非就是
函数的定义:

f x = x + 1

请注意，它们的语法为:

<identifier> arg1 arg2 ... argn = expr

模态卫队和 where声明。但是它们并不重要。
必须至少有一个论点的地方。
模式绑定(bind)是以​​下形式的声明:

<pattern> = expr

同样，模数卫队。
请注意，变量是模式，因此绑定(bind):

plus = (+)

是模式绑定(bind)。它将模式 plus(一个变量)绑定(bind)到表达式 (+)。
当模式绑定(bind)仅包含变量名时，称为
简单的模式绑定(bind)。
单态性限制适用于简单的模式绑定(bind)!
好吧，我们应该正式地说:

A declaration group is a minimal set of mutually dependent bindings.

report的第4.5.1节。
然后( report的第4.5.5节):

a given declaration group is unrestricted if and only if:

1. every variable in the group is bound by a function binding (e.g. f x = x)or a simple pattern binding (e.g. plus = (+); Section 4.4.3.2 ), and

2. an explicit type signature is given for every variable in the group thatis bound by simple pattern binding. (e.g. plus :: Num a => a -> a -> a; plus = (+)).

我添加的示例。
因此，受限声明组是一个组，其中有
非简单的模式绑定(bind)(例如 (x:xs) = f something或 (f, g) = ((+), (-)))或
有一些没有类型签名的简单模式绑定(bind)(如 plus = (+))。
单态性限制会影响 受限的声明组。
大多数时候，您不定义相互递归函数，因此不声明
组成为一个约束。
它有什么作用？
本节中的两个规则描述了单态性限制
report的4.5.5。
第一法则

The usual Hindley-Milner restriction on polymorphism is that only typevariables that do not occur free in the environment may be generalized.In addition, the constrained type variables of a restricted declarationgroup may not be generalized in the generalization step for that group.(Recall that a type variable is constrained if it must belong to sometype class; see Section 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

那么您将得到一个类型错误。因为当编译器看到 plus是
在 Integer声明中的 x上调用它将统一类型
带有 a的 Integer变量，因此 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 itmight 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)
  

对于这一点，我相信 wiki中的示例更加清晰。
考虑以下功能:

f xs = (len, len)
  where
    len = genericLength xs

如果 len是多态的，则 f的类型为:

f :: Num a, Num b => [c] -> (a, b)

因此，元组 (len, len)的两个元素实际上可能是
不同的值(value)观!但这意味着 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 sthe 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时必须以某种方式告诉编译器
它应该尝试解析哪种类型...
第二条规则

2. Any monomorphic type variables that remain when type inference for anentire module is complete, are considered ambiguous, and are resolvedto particular types using the defaulting rules (Section 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 -> Double和 x :: Double。
违约
如前所述，在 Section 4.3.4 of the Report中描述了一些默认规则，
推论者可以采用的方法，它将用单态类型替换多态类型。
只要类型不明确，就会发生这种情况。
例如在表达式中:

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

这里的表达式是模棱两可的，因为 show和 read的类型是:

show :: Show a => a -> String
read :: Read a => String -> a

因此， x的类型为 Read a => a。但是许多类型都满足此约束: Int， Double或 ()。选择哪一个？没有什么可以告诉我们的。
在这种情况下，我们可以通过告诉编译器所需的类型来解决歧义，
添加类型签名:

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是类的情况下，才出现在C类型的约束中。
(即，如果它显示为:Monad (m v)，则默认为，而不是)。

这些类中的至少一个是Num或Num的子类。

所有这些类均在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带有 extended defaulting rules(或 here for GHC8)，
也可以使用 ExtendedDefaultRules扩展名在文件中启用该功能。
默认类型变量不仅需要出现在约束中，而且所有
这些类是标准类，并且必须至少有一个类 Eq， Ord， Show或 Num及其子类。
此外，默认的 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约束导致
默认的 ()几乎没有用。
有用的链接
关于单态限制的资源和讨论很多。
以下是一些我认为有用的链接，这些链接可以帮助您理解或深入了解该主题:

Haskell的维基页面:Monomorphism Restriction

report

易于访问且美观的blog post

A History Of Haskell: Being Lazy With Class的第6.2节和第6.3节处理了单态性限制，并键入了默认的