Haskellの関数従属について

投稿者: | 2014年2月21日

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

関数従属性とは何か?

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の結果を得ることができるようになる。

参考情報

http://www.kotha.net/ghcguide_ja/7.6.2/type-class-extensions.html#functional-dependencies


http://rf0444.hatenablog.jp/entry/20120513/1336883141

http://www.haskell.org/haskellwiki/Functional_dependencies

注意

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

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

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

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です