什么是单态限制？

2018-05-31 14:56:31

我很困惑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' ？ plus应该有多态类型Num a => a -> a -> a ，我真的不知道这与sort类型有sort ，但只有sort会引发错误。

最后一件事：如果我评论sort文件编译的定义。但是，如果我尝试将它加载到ghci并检查我得到的类型：

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

为什么不是plus态的类型？

这是在元问题中讨论的有关Haskell单态限制的典型问题。

什么是单态限制？

Haskell wiki所述的单态限制是：

Haskell类型推断中的反直觉规则。如果您忘记提供类型签名，则有时此规则将使用“类型默认”规则将特定类型的自由类型变量填充。

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

我如何解决它？

首先，您始终可以明确提供类型签名，这样可以避免触发限制：

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

-- Runs as:
Prelude> plus 1.0 1
2.0

另外，如果你正在定义一个函数，你可以避免无点式，例如写：

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

您可能需要:set -XMonomorphismRestriction在较新的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中，有两种不同类型的绑定。函数绑定和模式绑定。函数绑定无非是一个函数的定义：

f x = x + 1

请注意，它们的语法是：

<identifier> arg1 arg2 ... argn = expr

模警卫和where的声明。但他们并不重要。

必须至少有一个参数。

模式绑定是一种形式的声明：

<pattern> = expr

再次，模数守卫。

请注意，变量是模式，所以绑定：

plus = (+)

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

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

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

那么，我们应该正式说：

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

报告第4.5.1节。

然后（报告第4.5.5节）：

给定的声明组是不受限制的，当且仅当：

组中的每个变量都被一个函数绑定（例如fx = x ）或一个简单的模式绑定（例如， plus = (+) ;第4.4.3.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的声明中看到通过Integer调用plus ，它将使用Integer来统一类型变量a ，因此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)

对于这一点，我相信维基的例子更清晰。考虑一下功能：

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是一个标准函数，其类型由签名给出

reads ::（Read a）=> String - > [（a，String）]

没有规则1， n将被分配类型∀ a. Read a ⇒ a ∀ a. Read a ⇒ a和s类型∀ a. Read a ⇒ String ∀ a. Read a ⇒ String 。后者是无效的类型，因为它本质上是不明确的。这是不可能在什么超载来确定使用s ，也可以通过增加一个类型的签名来解决s 。因此，当使用非简单模式绑定时（第4.4.3.2节），推断的类型在它们的约束类型变量中总是单态的，而不管是否提供了类型签名。在这种情况下， n和s都是单形a 。

那么，我相信这个例子是不言自明的。有些情况下，如果不将规则结果应用于类型歧义。

如果您按照上面的建议禁用扩展，则在尝试编译上述声明时将会出现类型错误。然而，这不是一个真正的问题：你已经知道使用read你必须以某种方式告诉编译器应该尝试解析哪种类型...

第二条规则

当整个模块的类型推断完成时，任何单形态类型变量都被认为是不明确的，并且使用默认规则解析为特定类型（见第4.3.4节）。

这意味着。如果你有你惯常的定义：

plus = (+)

这将具有类型Num a => a -> a -> a其中由于上述规则1， a是单形类型变量。一旦推断出整个模块，编译器将简单地选择一种类型，根据默认规则取代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 。

违约

如前所述，报告第4.3.4节中描述了一些违约规则，推理人可以采用并且将用单形态代替多态类型。只要类型不明确，就会发生这种情况。

例如在表达式中：

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 (mv)那么它是不可违约的）。

这些类中的至少一个是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带有扩展的默认规则（或者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

那个报告

一个可访问和不错的博客文章

Haskell历史第6.2节和第6.3节：懒惰与类一起处理单态限制和类型违约

链接地址: http://www.djcxy.com/p/7461.html

上一篇: What is the monomorphism restriction?

下一篇: How to type check recursive definitions using Algorithm W?