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并检查得到的类型：

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

为什么 ghci多态的类型不是？




这是关于Haskell中单态限制的规范问题
如 the meta question中所述。

Answer 1

什么是单态性限制？

Haskell Wiki指出的monomorphism restriction是：


Haskell类型推论中的违反直觉的规则。
如果您忘记提供类型签名，则有时该规则会被填写
使用“类型默认值”规则的具有特定类型的自由类型变量。


这意味着在某些情况下，如果您的类型不明确（即多态）
编译器将选择将该类型实例化为不明确的内容。

我如何解决它？

首先，您总是可以明确提供类型签名，这将
避免触发限制：

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两种不同类型。
函数绑定和模式绑定。函数绑定无非就是
函数的定义：

f x = x + 1

请注意，它们的语法为：

<identifier> arg1 arg2 ... argn = expr

模态守卫和 where声明。但是它们并不重要。

必须至少有一个论点的地方。

模式绑定是以​​下形式的声明：

<pattern> = expr

同样，模数卫队。

请注意，变量是模式，因此绑定：

plus = (+)

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

当模式绑定仅包含变量名时，称为
简单的模式绑定。

单态性限制适用于简单的模式绑定！

好吧，我们应该正式地说：


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


report的第4.5.1节。

然后（ report的第4.5.5节）：


在以下情况下，给定的声明组不受限制：


组中的每个变量都由函数绑定（例如 f x = x）绑定
或简单的模式绑定（例如 plus = (+)；第4.4.3.2节），以及
为该组中的每个变量给出一个显式的类型签名，
通过简单的模式绑定来绑定。 （例如 plus :: Num a => a -> a -> a; plus = (+)）。



我添加的示例。

因此，受限声明组是一个组，其中有
非简单的模式绑定（例如 (x:xs) = f something或 (f, g) = ((+), (-))）或
有一些没有类型签名的简单模式绑定（如 plus = (+)所示）。

单态限制会影响受限制的声明组。

大多数时候，您不定义相互递归函数，因此不声明
组成为一个约束。

它有什么作用？

本节中的两个规则描述了单态性限制
report的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

那么您将得到一个类型错误。因为当编译器看到 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。

基本原理

该报告说：


需要规则1的原因有两个，两者都很微妙。


规则1防止意外重复计算。
例如， genericLength是标准函数（在库 Data.List中）
其类型由

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

现在考虑以下表达式：

let len = genericLength xs
in (len, len)

看来 len应该只计算一次，但如果没有规则1，
可能会被计算两次，两次分别在两个不同的重载中进行。
如果程序员确实希望重复计算，
可以添加显式类型签名：

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)的两个元素实际上可能是
不同的价值观！但这意味着 genericLength完成的计算
必须重复以获得两个不同的值。

这里的基本原理是：代码包含一个函数调用，但不引入
此规则可能会产生两个隐藏的函数调用，这是非常直观的。

在单态限制下， f的类型变为：

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

这样，无需多次执行计算。



规则1避免歧义。例如，考虑声明组

[（n，s）] =读取t

回想 reads是一个标准函数，其类型由签名给出

读取::（读取a）=>字符串-> [（a，String）]

如果没有规则1，将为 n指定类型 ∀ a. Read a ⇒ a和 s
类型 ∀ a. Read a ⇒ String。
后者是无效类型，因为它本质上是模棱两可的。
无法确定在什么重载下使用 s，
也不能通过为 s添加类型签名来解决。
因此，当使用非简单的模式绑定时（第4.4.3.2节），
推断出的类型在其受约束的类型变量中总是单态的，
不管是否提供类型签名。
在这种情况下， n和 s在 a中都是单态的。



好吧，我相信这个例子是不言而喻的。有些情况下没有
应用规则会导致类型不明确。

如果按照上述建议禁用扩展名，则在
试图编译以上声明。但是，这并不是真正的问题：
您已经知道使用 read时必须以某种方式告诉编译器
它应该尝试解析哪种类型...

第二条规则



在对类型进行类型推断时保留的所有单态类型变量
整个模块是完整的，被认为是模棱两可的，并且已经解决
使用默认规则（第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的子类。
所有这些类均在Prelude或标准库中定义。


默认类型变量由 Num列表中的第一个类型替换
这是所有歧义变量类的实例。

默认的 default声明为 default。

例如：

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

请注意，这解释了为什么在问题示例中仅 default (Integer, Double)
定义引发错误。类型 sort不能默认
因为 Ord a => [a] -> [a]不是数字类。

扩展默认

请注意，GHCi随附 extended defaulting rules（或 here for GHC8），
也可以使用 Ord扩展名在文件中启用该功能。

默认类型变量不仅需要出现在约束中，而且所有
这些类是标准的，并且必须至少有一个类
ExtendedDefaultRules， Eq， Ord或 Show及其子类。

此外，默认的 Num声明为 default。

这可能会产生奇怪的结果。以问题为例：

Prelude> :set -XMonomorphismRestriction
Prelude> import Data.List(sortBy)
Prelude Data.List> let sort = sortBy compare
Prelude Data.List> :t sort
sort :: [()] -> [()]

在ghci中，我们没有收到类型错误，但是 default ((), Integer, Double)约束导致
默认值 Ord a几乎没有用。

有用的链接

关于单态限制的资源和讨论很多。

以下是一些我认为有用的链接，这些链接可以帮助您理解或深入了解该主题：


Haskell的Wiki页面： Monomorphism Restriction
report
可访问且美观的 blog post
A History Of Haskell: Being Lazy With Class的6.2和6.3节处理了单态性限制和类型默认值