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 之间的不同行为是由于不同
默认规则。
它什么时候发生？
在 Haskell 中，根据 report 的定义，有两种不同类型的 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 = (+) )。
单态限制影响 受限的 声明组。
大多数情况下，您没有定义相互递归函数，因此没有定义声明
group 变成了一个绑定(bind)。
它有什么作用？
单态限制在节中由两条规则描述
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 扩展名在文件中启用。
默认类型变量不仅需要出现在所有
类(class)是标准的，必须至少有一个类(class)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 节处理单态限制和类型默认