型クラスあり実装を、型クラスなし実装に変換する
Haskellの型クラスはコンパイル時に型クラスなしの等価なプログラムに変換される
脱糖後のコードはHindley-Milner型推論できる
各型クラス宣言に対して、以下のものを導入する
メソッド辞書になる型
そのメソッドにアクセスする関数群
例として以下のような
Num 型クラスを考える元のコード.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 型変換後.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の使用は以下のように変換できる変換
| 元のコード | 変換後のイメージ |
| x+y | add numD x y |
| x*y | mul numD x y |
| nagate x | neg numD x |
add や mul は型クラス宣言の変換時に作った関数ここでは
x や y の型は Int か Float 具体的な型を入れるてみると
変換
| 元のコード | 変換後 |
| 3 + 3 | add numDInt 3 3 |
| 3.14 * 3.14 | mul numDFloat 3.14 3.14 |
ここで
numDInt などが使われる使用箇所の変換
元のコード.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)変換後.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)美しすぎる..
squares の変換も、『How to make ad-hoc polymorphism less ad hoc』の2節の「Arithmetic」のところで言われていたような問題点が解消されている squares' の引数にとる型の組み合わせが増えるとoverload用に生成される関数が指数関数的に増えるというもの上の様な変換により
square 'a' のように Char を引数にとっても、 NumDChar が存在しないため、ちゃんと型エラーになる (==) について元のコード.hsclass 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 のときと同じ変換後.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リスト型に対して
元のコード
元のコード.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] にできる変換後
変換後.hseqDList :: 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つの関数が生成される
変換
| 元のコード | 変換後 |
| "hello" == "goodbye" | eq (eqDList eqDChar) "hello" "goodbye" |
| `member ["Haskell", "Alonzo"] "Moses"` | `member' (eqDList eqDChar) ["Haskell", "Alonzo"] "Moses"` |
タプルに対して
元のコード.hs-- タプルをインスタンスに
instance Eq a, Eq b => Eq (a,b) where
(u,v) == (x,y) = (u == x) & (v == y)変換後.hseqDPair :: (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自作型に対して
元のコード.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 に対する == の定義は、前者のリストの任意の要素が、後者のリストに含まれる
かつ、逆も成り立つ