関数従属(和訳)
FunctionalDependencies
6.8.1以降
型クラス宣言における関数従属の使用を許可する．
関数従属は，Mark Jonesの関数従属と型クラスに記述されているように実装されている． 関数従属は，型クラス宣言の構文の中に縦線で示される．例えば：
code: fd1.hs
class (Monad m) => MonadState s m | m -> s where ...
class Foo a b c | a b -> c where ...
関数従属の規則
型クラス宣言では，すべての型クラスの型変数は各メソッドの型の自由変数から(型シグネチャの文脈で述べた意味で)到達可能でなければない．例えば：
code: fd2.hs
class Coll s a where
empty :: s
insert :: s -> a -> s
はemptyの型がaについて言及していないので，違法である．関数従属は，型変数を到達可能にすることができる：
code: fd3.hs
class Coll s a | s -> a where
empty :: s
insert :: s -> a -> s
代わりにCollは次のように書き直しても良い：
code: fd4.hs
class Coll s a where
empty :: s a
insert :: s a -> a -> s a
そのコレクション型a 'S(すなわち, (s a) )と要素の型aの間の関係を作っている．時折これは実際には動作しない．その場合はこのようにクラスを分割することができる：
code: fd5.hs
class CollE s where
empty :: s
class CollE s => Coll s a where
insert :: s -> a -> s
関数従属の背景
関数従属の動機と使用法に関する以下の説明は，Hugsのユーザーマニュアルから引用したもので，Mark Jonesの許可を得てここに(少し変更を加えて)引用している．
コレクション型のライブラリの一部として意図された次の型クラスを考えよう．
code: fd6.hs
class Collects e ce where
empty :: ce
insert :: e -> ce -> ce
member :: e -> ce -> Bool
ここで使用されている型変数eは要素の型を表し，ceはコンテナ自体の型を表す．このフレームワーク内で，リストまたは特性関数(いずれも同等の型の集合を表す)，ビットセット(文字の集合を表す)，または連想配列(要素がハッシュ関数を持つ任意のコレクションを表す)用にこのクラスのインスタンスを定義したいかもしれない．標準実装の詳細を省略すると，次のような宣言とでもなるだろう：
code: fd7.hs
instance Eq e => Collects e e where ... instance Eq e => Collects e (e -> Bool) where ...
instance Collects Char BitSet where ...
instance (Hashable e, Collects a ce)
=> Collects e (Array Int ce) where ...
我々には型クラスがあり、一通りの面白い実装もあるので，これらの定義はすべてとても良さそうに見える．残念ながら，この型クラス宣言には深刻な問題がいくつかある．まず，emptyの型は曖昧である：
code: fd8.hs
empty :: Collects e ce => ce
「曖昧」とは，記号=>の左側には登場しているが右側には登場していない型変数eがあることを意味している．これの問題点は，Haskellのオーバーロードの理論的な基礎によれば，曖昧な型を持つすべての項に対してセマンティクスがwell-definedであることを保証できない点である．
この問題そのものは，型クラス宣言からemptyを削除することで回避することができる．しかし，残りのメソッドであるinsertとmemberには曖昧な型はないが，それらを使おうとするとまだ問題が発生する．たとえば，次の2つの関数を考える：
code: fd9.hs
f x y = insert x . insert y
g = f True 'a'
GHCは以下の型を推論する：
code: fd10.hs
f :: (Collects a c, Collects b c) => a -> b -> c -> c
g :: (Collects Bool c, Collects Char c) => c -> c
fの型では，2つの値それぞれを同じコレクションに順番に挿入しようとしても，2つの引数xとyに異なる型を割り当てられてしまう．1種類の値のみを含むコレクションをモデル化しようとしている場合，これは明らかにおかしな挙動である．さらに悪いことに，型エラーを引き起こさずに，gが定義できてしまう．結果として，このコードのエラーは定義した時点では発生しない．代わりに，gを使用しようとしたときにのみ発生する．定義と呼び出し場所が異なるモジュール内にある可能性もあるわけで，これはとてもマズい．
コンストラクタクラスを使おうとする試み
上記の問題に直面して，何人かのHaskellプログラマは次のような型クラス宣言のようなものを使いたくなるかもしれない：
code: fd11.hs
class Collects e c where
empty :: c e
insert :: e -> c e -> c e
member :: e -> c e -> Bool
先ほどとの主な違いは，元の型クラス宣言でceで表されるコレクション型自体ではなく，コレクション型c eを形成するために使用される型コンストラクタcを抽象化するしている点である．これにより，前述したような直接的な問題が回避される．emptyは型がCollects e c => c eになり，あいまいさはない．
前節の関数fは，より正確な型を持つことになる：
code: fd12.hs
f :: (Collects e c) => e -> e -> c e -> c e
fの型は2つの引数が異なる型を持つことを許可していないため，前節の関数gは期待通りに型エラーで拒否される．よって，これは，あいまいさの問題なしに，実際に非常にうまく機能する複数パラメータの型クラスの例である．しかし，落とし穴がある．このバージョンのCollectsクラスは元のクラスほど一般的ではない．というのも，このバージョンのCollectsクラスは，前節で与えられたCollectsの4つのインスタンスの一つだけしか使うことができない．なぜなら，ある型コンストラクタをc，要素の型をeとしたときに，それらのうちの一つ(Listのインスタンス)だけしかc eという形式でコレクション型を書くことができないためである．
関数従属を追加する
Collectsクラスのより有用なものを定義するために，GHCはプログラマが複数パラメータクラスのパラメータ間の依存関係を指定することを可能にする機能を提供している(理論的基礎と先行研究に興味がある読者のために：依存関係に関する情報を使用するということは，Chen，Hudak，Oderskyによって提唱された「パラメトリック型クラス」の提案の一般化，または修飾型(qualified type)の「改善」のためのMark Jonesの後期のフレームワークの特別な場合の両方として見ることができる．根本的な考えはJonesの草稿 の中でより理論的で抽象的な設定でも議論されている．そこではそれらは暗黙にパラメータ化されたシステムでの一般的な設計空間の一点として認識される)． 抽象的な例から始めるために，次のような型クラス宣言を考える：
code: fd13.hs
class C a b where ...
これは，Cは型(またはaとbの種によっては型コンストラクタ)上の二項関係として考えることができることを簡単に示している．次の例のように，パラメータ間の依存関係に関する情報を追加するために、型クラスの定義に追加の句を含めることができる：
code: fd14.hs
class D a b | a -> b where ...
class E a b | a -> b, b -> a where ...
記法a - > bは|とwhereの間で使われる(関数型と混同しないこと)．これは，パラメータaから一意にパラメータbが決定することを示しており，ちょうど「a がbを決定する」と読んでも良い．したがって，Dはただの関係ではなく，実は(部分)関数である．同様に，Eの定義に含まれている2つの依存関係から，Eは型間の(部分的な)1対1の写像を表していることがわかる．
より一般的には，依存関係はx1 ... xn -> y1 ... ymのような形式をとる．ここで，x1, ..., xnおよびy1, ..., ym(訳注: 原文が誤字っているので直した)は，n > 0かつm >= 0とした型変数であり，パラメータyがパラメータxによって一意に決定されるということを意味する．t -> a bのように，依存関係の片側に複数の型変数がある場合は，スペースを区切り文字として使用できる．上記のEの定義のように，型クラスは区切り文字としてカンマを使用して複数の依存関係の注釈を付けられることに注意せよ．この記法で書くことができるいくつかの依存関係は冗長であり，それらは全く実用的ではなく，代わりにプログラムのエラーを起こすかもしれないので拒絶されるだろう．このような依存関係の例としては，a -> a, a -> a a,a ->などがある． 複数の依存関係が与えられている場合も同様に，いくつかの冗長な注釈が存在する(例：a -> b, b -> c, a -> c など)．そのよう場合はいくつかのサブセットが残りの依存関係を暗示している．このような例はエラーにはならない．依存関係は型クラス宣言にのみ現れ，言語の他の部分には現れないことに注意すること．特に，インスタンス宣言，型クラス制約，型の構文はまったく変わらない．
型クラス宣言に依存関係を含めることによって，プログラマが各複数パラメータ型クラスをより正確に指定するための機能を提供する．一方，コンパイラは，プログラム内の任意の時点で有効範囲内にある一連のインスタンスが，宣言されている依存関係と一致していることを確認する責任がある．たとえば，次の2つのインスタンス宣言は，どちらか一方を使うことはできても，Dの依存関係に違反しているため，同じスコープ内に一緒に現れることはできない：
code: fd15.hs
instance D Bool Int where ...
instance D Bool Char where ...
また，次の宣言は，それ自体でも許可されていないことにも注意せよ：
code: fd16.hs
ここでの問題は、このインスタンスが[a]の 1つの特定の選択をbの複数の選択と関連付けることを可能にすることであり，これはDの定義で指定された依存性と矛盾する(訳注：つまりはbがaによって一意に決まることがこのインスタンス宣言からは保証されていないので違法であるということ)．より一般的には，これは、どのインスタンスの形式でも，次のことを意味する：
code: fd17.hs
instance D t s where ...
いくつかの特定の型tとsのとき，sに現れることができる唯一の型変数はtに現れるものである．そうであれば，型変数tを知っていれば，sは唯一に決定されるだろう．
依存関係情報を含めることの利点は，あいまいさの問題なしに，そしてより正確な型の利点をもって，より一般的な複数パラメータの型クラスを定義できることである．これを説明するために，コレクションクラスの例に戻り，Collectsの元の定義に単純な依存関係の注釈を付ける：
code: fd18.hs
class Collects e ce | ce -> e where
empty :: ce
insert :: e -> ce -> ce
member :: e -> ce -> Bool
ここでの依存関係ce - > eは，要素の型eがコレクションceの型によって一意に決まること指定している．Collectsの両方のパラメータの種はTypeである．ここにはコンストラクタクラスはない．先に挙げたCollectsのすべてのインスタンスは，この新しい定義と一緒に使える．
元の定義で発生したあいまいさの問題はどうだろうか．emptyはまだ型Collects e ce => ceを持っているが，あいまいな型と見なす必要はもうない．型変数eは記号=>の右側には現れないが，型クラスCollectsの依存関係は，記号=>の右側に現れるceによって型変数eが一意に決定されることをコンパイラに教える．したがって，emptyが使用される文脈では，ceとeの両方の型を決定するのに十分な情報が得られる．もっと一般的に言うと，=>の左側に型変数が含まれていて，それが右側の変数によって(直接的にも間接的にも)一意的に決定されない場合のみ，型があいまいであると見なされる．
また，依存関係は，ユーザ定義関数に対してより正確な型を生成するのに役立つ．したがって，エラーを早期に検出し，プログラマが作業する上での雑然とした型を少なくすることができる．関数fの前の定義を思い出そう：
code: fd19.hs
f x y = insert x y = insert x . insert y
我々はもともとの型はこうだった：
code: fd20.hs
f :: (Collects a c, Collects b c) => a -> b -> c -> c
Collectsの依存関係を考えると，aとbは同じ最初のパラメータcを持つCollects制約の 2番目のパラメーターとして現れるため，同じである必要がある．したがって，fのより短くより正確な型を推論することができる：
code: fd21.hs
f :: (Collects a c) => a -> a -> c -> c
同様に，以前のgの定義は型エラーとして検出される．
ここではほんの少しの例を挙げたが，依存情報を追加することで，実際に複数のパラメータクラスをより有用にし，あいまいさの問題を避け，より一般的なインスタンス宣言を行うことができる．