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 fill the 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 that is 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 type variables that do not occur free in the environment may be generalized. In addition, the constrained type variables of a restricted declaration group may not be generalized in the generalization step for that group. (Recall that a type variable is constrained if it must belong to some type 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 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)
  

对于这一点，我相信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 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时必须以某种方式告诉编译器
它应该尝试解析哪种类型...

第二条规则

2. Any monomorphic type variables that remain when type inference for an entire module is complete, are considered ambiguous, and are resolved to 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节处理了单态性限制并键入了默认的