2013-04-17
■ [haskell][types] Haskellの型クラスの実現方法について調べてみた
型クラスの実装について調べていたら、1988年の「How to make ad-hoc polymorphism less ad hoc」という論文に行き当たった。
- http://homepages.inf.ed.ac.uk/wadler/topics/type-classes.html (How to make ad-hoc polymorphism less ad hoc) (Macだとpsファイルがそのまま開けるようです)
これによると、型クラスを使ったHaskellプログラムは、型クラスを使わない(代数的データ型のみの)プログラムに変換できるそうだ。*1
内容は、Haskellのclass構文とinstance構文の使い方を知っている人なら、上から順に読んでいけば理解できると思います。実装の話は3章からです。
最後のConclusionでは「型クラスはbounded quantierの一種と考えることができるが〜」のような専門用語が出てきますが、そのあたりが気になる人は「型システム入門」(TAPL)を読みましょう。*2
4274068854
4274069117
ad-hoc polymorphismとは
1章に説明がある。length [1,2,3]とlength [1.1, 1.2, 1.3]のような形のpolymorphismでは、length自体の実装はリストの中身がIntでもFloatでも同じで、パラメータとなる型の名前が変化するだけだ。こういうものをparametric多相という。
一方で、33と33.14では、乗算演算子はIntとFloatで実装が全く違う。こういうものをad-hoc多相という。
例
この論文では、Numの例とEqの例が出てくる。Numは「掛け算や足し算の演算子を、IntでもFloatでも使えるようにしたい」、Eqは「比較演算子を、IntでもFloatでも使えるようにしたい」という話。(型クラスを使うとIntやFloatに限らず、ユーザ定義の型にも+や==を定義できる)
変換の概要
class宣言は、型が持たないといけないメソッド一覧を定義する。それに対しinstance宣言は、実際にメソッドとして振る舞う関数群を与える。なので、これを代数データ型として定義してやる。
-- 足し算関数と掛け算関数を保持するデータ型を定義
data NumDict a = NumDict (a->a->a) (a->a->a)
-- Int用のメソッド群はこれ
NumDInt = NumDict addInt mulInt
-- Float用のメソッド群はこれ
NumDFloat = NumDict addFloat mulFloat</pre>
+や*を実行するには、実際のメソッド関数が必要になる。なので、NumDictを第一引数にとる補助関数を作り、プログラム中での(+)や(*)の呼び出しをそれの呼び出しへと置き換えてやる。
プログラム中の(+)や(*)がIntを扱うのか、Floatを扱うのかは、型推論で分かっているはずなので、こういう変換ができる。
という感じ。
論文を読んでたときのメモが https://gist.github.com/yhara/5401423 にあります(あまり他の人の参考にはならないと思いますが)。