[解決済み] 単相制限とは何ですか？

2023-06-30 15:52:02

質問

haskellコンパイラが、例えばポイントフリー定義を使用したときに、期待したよりも多相ではない型を推論することがあることに困惑しています。例えば、ポイントフリー定義を使用するとき、私が期待するものよりポリモーフィックでないタイプを推論することに困惑しています。

それは、古いバージョンのコンパイラーでデフォルトでオンになっている "monomorphism restriction" に問題があるように思われます。これは、古いバージョンのコンパイラーでデフォルトでオンになっています。

次のような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 を異なるタイプで2回呼び出そうとすると同じことが起こります。

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の単相性制限に関する典型的な質問です。
で説明されているように

メタな質問

.}

どのように解決するのですか？

単相制約とは何ですか？

この単同型制約は、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

オフにする

この制限を単純に無効化することができます。をする必要がありません。動作は2つの拡張機能によって制御されます。 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
が必要かもしれません。}

そして実際、私たちはその型が 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で定義しようとするとを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 項の報告 ):

は、与えられた宣言グループが 無制限 である場合のみ。

は、グループ内のすべての変数が関数バインディング（例えば f x = x ) または単純なパターンバインディング（例えば plus = (+) 4.4.3.2節），及び

単純なパターンバインディングで束縛されるグループ内のすべての変数に対して、明示的な型署名が与えられる。は単純なパターンバインディングによって束縛されます。(例 plus :: Num a => a -> a -> a; plus = (+) ).

^{私が追加した例です。}

では 制限される 宣言グループは 非単純 パターンバインディングがあるグループです (例 (x:xs) = f something または (f, g) = ((+), (-)) のように）、あるいは型署名のない単純なパターンバインディングがある場合（例えば plus = (+) ).

単相関の制限は 制限される 宣言群に影響します。

ほとんどの場合、相互再帰的な関数を定義することはないので、宣言グループグループは単なる a バインディングになります。

何をするものですか？

単相の制限は、以下の2つのルールで記述されています。 4.5.5節にある報告 .

最初のルール

通常のHindley-Milnerによる多相性の制限は、環境中で自由に出現しない型変数だけが汎化されることです。変数のみが汎化されるというものです。さらに 制限付き宣言グループの制約付き型変数グループの制約付き型変数は、そのグループの汎化ステップで汎化されないかもしれません。 (ある型変数がある型クラスに属さなければならない場合、型変数は制約されることを思い出してください。に属さなければならない場合、型変数は制約されることを思い出してください。）

ハイライトされた部分は単相制約が導入されたものです。これはもしが多相型である場合（つまり、何らかの型変数を含んでいる場合）にはとその型変数が制約されている（つまり、その型変数にクラス制約がある。例えば，型 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が必要な理由は2つあり、どちらもかなり微妙なものです。
ルール 1 は、計算が予期せず繰り返されることを防ぎます。例えば genericLength は標準的な関数（ライブラリでは Data.List ) で与えられ、その型は
  genericLength :: Num a => [b] -> a
ここで、次のような式を考えてみましょう。
  let len = genericLength xs
  in (len, len)
まるで len は一度だけ計算されるはずですが ルール1がなければは2回、2つの異なるオーバーロードのそれぞれで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)

ということで、タプルの2つの要素 (len, len) は実際には 異なる の値である可能性があります。しかし、これでは genericLength はを繰り返すと、2つの異なる値が得られます。

ここでの根拠は、コードに 1 関数呼び出しがありますがを生成する可能性があります。 2 を生成する可能性があり、直感的ではありません。

単相関の制限で f になる。

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

このように、何度も計算を行う必要はありません。

ルール1は曖昧さを防ぐものです。例えば、次のような宣言群を考えてみましょう。
 [(n,s)] = reads t
思い出してみてください。 reads は標準的な関数で、その型はシグネチャである
 reads :: (Read a) => String -> [(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 は モノモルフィック 型変数です。モジュール全体が推論されるとが推論されると、コンパイラは単純にその 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 (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には が拡張されています。 デフォルトのルール (または 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 :: [()] -> [()]

では、型エラーは発生しませんが Ord a 制約の結果はのデフォルトは () となり、かなり使い物になりません。

便利なリンク集

以下のようなものがあります。 たくさん のリソースがあり、単相制約について議論されています。

以下は、私が役に立つと思うリンクで、このトピックを理解したり、さらに深く掘り下げるのに役立つと思われるものです。

Haskell の wiki ページです。単相関の制限
は報告
アクセシブルで素敵なブログ記事
の 6.2 節と 6.3 節は Haskellの歴史。クラスで怠けるは、単相制約と型デフォルトを扱っています。