Haskellの関数従属について

やっと分かった気がするのでまとめる。

関数従属性とは何か？

Parsecライブラリなどを見ていると型クラスのインスタンス宣言に関数従属性が記述されていることがある。

instance Moge a b c | a b -> c

といった感じだ。|から右側が従属性を表している。
a, bの型からcの型を導出して良いということをコンパイラに示すためのものである。

まず、これが必要になる局面としては、型クラスに複数の型変数を指定できる場合にのみ必要である。

{-# LANGUAGE MultiParamTypeClasses #-}
class Mult a b c

となっているような場合である。

この時

instance Multi Matrix Matrix Matrix

として

m1 :: Matrix
m2 :: Matrix
(m1 * m2)

というプログラムを動かすと、m1 * m2 でエラーとなる。
これは、コンパイラがinstanceを定めるときにMulti a b c のうち、a = Matrix, b = Matrixというところまで決めることができる。しかし、cを決めることができないため、c の型を決めることができない。

instanceのうちa, bがMatrixとなっているinstanceは一つしかないから推論してほしいと考えたが、実際それは誤りである。

コンパイラの立場では他の翻訳単位にa = Matrix, b = Matrix, c = Intなるinstanceがないことを保証することができないからである。

(m1 * m2) :: Matrix

とコンパイラにわかるように記述すると上手く動作するようになる。

ここで問題を整理する。

そこで、書き手側がコンパイラに勝手に型を定めて良いとするような記述が関数従属性である。
関数従属性をを追加すると型変数a, bの型が定まったらそこから導かれる型変数cの型を推論してよいという規則を追加する。

ここでは、関数従属性を追加することで、意図通りにm1 * m2の結果の型を明示することなくMatrixの結果を得ることができるようになる。

注意

最後のHaskellWikiの情報には誤りがあった。

(m1 * m2) :: Matrix * m3 — this is ok
と書いてあるが、これはOKではない。

実際型を見てみると、c の型は曖昧なままとなってしまっているため型エラーである。
説明内容は上手く書いてあるように見えるので参考情報として上げておく。