How to make ad-hoc polymorphism less ad hoc を読んだ

September 26, 2017

Rustの型システムの参考論文として紹介されている論文2つ目。Wadler先生の有名なやつ。

読んだ。。読んだけど、このQiitaがとても良くまとまっているので、内容をさらうならこれらを読むのが良さそう。

とりあえず自分用に知らなかったところや大まかな流れのメモだけ書いておく。

構成

  1. オーバロード便利だけど、オーバーロードだと組み合わせによって数がexponentialに増えてしまうので問題がある
  2. 回避策としての型クラス
  3. 型クラスのセマンティクスは、型クラスを使わない形への変換を定義することで定義する。これによりH/M型システムで扱える。
  4. 例えばEqについて、Eq aがあればPair aやList aに対しても Eqが考えられる
  5. さらに型クラスでサブクラスの関係を考えることができる
  6. 最後におまけでFormalに型システムについて書いてある

型クラスへのモチベーション / オーバーロードの問題点

例えば掛け算 * は整数と浮動小数点数で使える。

  • 3 * 2
  • 3.0 * 3.14

けど、例えばこんな(多相な)関数は定義できない。

square x = x * x

一般的な解決策として、各型ごとに square を定義していく方法がある。 でも例えばこんな関数があった場合は数がexponentialに増える。

squares (x, y, z) = (square x, square y, square z)

また、別の例として == を考えてみる。

  • すべての型に対して(オーバーライドで) == を考えていくのは辛い。特に多相な型だとすべて定義していくのは無理っぽい。
  • 完全に == を 多相にしたとすると、関数型や抽象型を渡したときに問題が起こる

解決策として型クラスを導入した。

型クラスを使わない形への変換について

上のQiitaから引用。

オブジェクト指向における関数ポインタの辞書を文字通り Haskell におけるデータ型の辞書として読み替えて この辞書を型に応じて挿入する というものでした

具体的にEqについて型クラスを使わない形で書いて見ると、

-- 比較用の関数を保持する型
EqD a = EqDict (a -> a -> Bool)

-- EqDictから比較関数を取り出す関数
eq (EqDict e) = e

-- Intに対するEqDとして、あらかじめ用意したeqIntを使うよ、という意味
eqDInt :: EqD Int
eqDInt = EqDict eqInt

これらを使って、コンパイル時に以下の変換を行う。

3 * 4 == 12
	--> eq eqDInt (mul numDInt 3 4) 12

感想

すでに多少知識がある話だったのと、内容も(最後のおまけ部分をのぞけば)そんなに重たくないので、リージョンのときよりさらっと読めた。気がする。

このエントリーをはてなブックマークに追加