型クラスあり実装を、型クラスなし実装に変換する

『How to make ad-hoc polymorphism less ad hoc』の4節を噛み砕く

Haskellの型クラスはコンパイル時に型クラスなしの等価なプログラムに変換される

脱糖後のコードはHindley-Milner型推論できる

各型クラス宣言に対して、以下のものを導入する

メソッド辞書になる型

そのメソッドにアクセスする関数群

例として以下のようなNum型クラスを考える

code:元のコード.hs

-- 型クラス宣言

class Num a where

(+), (*) :: a -> a -> a

negate :: a -> a

-- インスタンス宣言

instance Num Int where

(+) = addInt

(*) = mulInt

negate = negInt

instance Num Float where

(+) = addFloat

(*) = mulFloat

negate = negFloat

上の様な型クラスNumを型クラスなしに変換したものが以下のNumD型

code:変換後.hs

-- Num型クラス宣言を変換

data NumD a = NumDict (a -> a -> a) (a -> a -> a) (a -> a)

add (NumDict a m n) = a

mul (NumDict a m n) = m

neg (NumDict a m n) = n

-- instance宣言を変換

numDInt :: NumD Int

numDint = NumDict addInt mulInt negInt

numDFloat :: NumD Float

numDFloat = NumDict addFloat mulFloat negFloat

型クラス宣言の変換の箇所

NumDict型コンストラクタは3つの要素を持つ

a->a->a、a->a->a、a->aの部分

これはNumのmethodの(+)、(*)、negateを表す

add、mul、neg関数は、NumD aを引数に取り、

それぞれNumDictの1番目、2番目、3番目を返す

これが「メソッドにアクセスする関数群」

インスタンス宣言の変換の箇所

インスタンスになる型一つに対して一つのNumDict型の値を定義する

ここではIntに対して、NumD Int型のnumDictという値を定義している

Num型クラスの各methodの使用は以下のように変換できる

table:変換

元のコード変換後のイメージ

x+y add numD x y

x*y mul numD x y

nagate x neg numD x

addやmulは型クラス宣言の変換時に作った関数

ここではxやyの型はIntかFloat

具体的な型を入れるてみると

table:変換

元のコード変換後

3 + 3 add numDInt 3 3

3.14 * 3.14 mul numDFloat 3.14 3.14

ここでnumDIntなどが使われる

使用箇所の変換

code:元のコード.hs

-- 型クラス制約のある関数定義

square :: Num a => a -> a

square x = x * x

squares :: Num a, Num b, Num c => (a, b, c) -> (a, b, c)

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

code:変換後.hs

-- 使用箇所を変換

square' :: NumD a -> a -> a

square' numDa x = mul numDa x x

squares' :: (NumD a, NumD b, NumD c) -> (a, b, c) -> (a, b, c)

squares' (numDa, numDb, numDc) (x, y, z)

= (square' numDa x, square' numDb y, square' numDc z)

美しすぎる..mrsekut.icon*3

squaresの変換も、『How to make ad-hoc polymorphism less ad hoc』の2節の「Arithmetic」のところで言われていたような問題点が解消されている

ref アドホック多相と型クラスらへん#5eaebf74198270000097de72

squares'の引数にとる型の組み合わせが増えるとoverload用に生成される関数が指数関数的に増えるというもの

上の様な変換によりsquare 'a'のようにCharを引数にとっても、NumDCharが存在しないため、ちゃんと型エラーになる

(==)について

code:元のコード.hs

class Eq a where

(==) :: a -> a -> Bool

instance Eq Int where

(==) = eqInt

instance Eq Char where

(==) = eqChar

member :: Eq a => a -> a -> Bool

member [] y = False

member (x:xs) y = (x == y) \/ member xs y

ここまではNumのときと同じ

code:変換後.hs

-- Eq型クラス宣言を変換

data EqD a = EqDict (a -> a -> Bool)

eq (EqDict e) = e

-- Int, Charのインスタンス宣言を変換

eqDInt :: EqD Int

eqDInt = EqDict eqInt

eqDChar :: EqD Char

eqDChar = EqDict eqChar

-- 使用箇所を変換

member' :; EqD a -> a -> a -> Bool

member' eqDa [] y = False

member' eqDa (x:xs) y = eq eqDa x y \/ member' eqDa xs y

リスト型に対して

元のコード

code:元のコード.hs

-- リストをインスタンスに

instance Eq a => Eq a where

[] == [] = True

[] == y:ys = False

x:xs == [] = False

x:xs == y:ys = (x == y) & (xs == ys)

インスタンスにする際の制約がある

aがEqのインスタンスなら、Eq [a]にできる

変換後

code:変換後.hs

eqDList :: EqD a -> EqD a

eqDList eqDa = EqDict (eqList eqDa)

eqList :: EqD a -> a -> a -> Bool

eqList eqDa [] [] = True

eqList eqDa [] (y:ys) = False

eqList eqDa (x:xs) [] = False

eqList eqDa (x:xs) (y:ys) = eq eqDa x y & eq (eqDList eqDa) xs ys

インスタンスにする際の制約がある場合は、それを表現するために2つの関数が生成される

table:変換

元のコード変換後

"hello" == "goodbye" eq (eqDList eqDChar) "hello" "goodbye"

member ["Haskell", "Alonzo"] "Moses" member' (eqDList eqDChar) ["Haskell", "Alonzo"] "Moses"

タプルに対して

code:元のコード.hs

-- タプルをインスタンスに

instance Eq a, Eq b => Eq (a,b) where

(u,v) == (x,y) = (u == x) & (v == y)

code:変換後.hs

eqDPair :: (EqD a, EqD b) -> EqD (a,b)

eqDPair (eqDar, eqDb) = EqDict (eqPair (eqDa, eqDB))

eqPair :: (EqD a, EqD b) -> (a,b) -> (a,b) -> EqD (a,b)

eqPair (eqDar, eqDb) (x,y) (u,v) = eq eqDa x u & eq eqDb y v

自作型に対して

code:元のコード.hs

-- 自作型Setをインスタンスに

data Set a = MkSet a

instance Eq a => Eq (Set a) where

MkSet xs == MkSet ys =

and (map (member xs) ys) & and (map (member ys) xs)

集合を表す、自作型のSetに対する==の定義は、

前者のリストの任意の要素が、後者のリストに含まれる

かつ、逆も成り立つ