第3章

3.1

代数的データ型と型クラス

代数的データ型の定義

リストのようなデータ型をプログラマがあらたに定義する方法も用意されている。このようなデータ型は複数のを持つことができる。このようなデー
タ型を（ algebraic datatype ）という。
データ型の宣言の一般的な形式は次のとおりである。

data 型構成子名 型引数 1 型引数 2 . . .
= 構成子名 1 型 1,1 . . . 型 1,n1
| 構成子名 2 型 2,1 . . . 型 2,n2
| ...
| 構成子名 m 型 m,1 . . . 型 m,nm型引数 k型構成子名・構成子名ともに使える文字は変数名の場合と同じだが 、変数名とは逆にから始まる必要がある。この型は 構成子名1 〜 構成子名m のm 個の種類のデータからなる。型m,1 , . . . , 型m,nm は 構成子名m が持つフィールドの型である。型引数1 , 型引数2 , . . . , 型引数k はフィールド の中に現れうる型変数である。| は “または ” と読む例えば

1

data Foo x y = Alice x [y] | Bob String y | Charlieというデータ型の場合、Foo Double Int 型になるのは次のような式である、Alice
3.14 [1,2], Bob "Hello" 3, Charlie, . . . 。
代数的データ型は構成子にパラメータがない場合は、C や Java の列挙（ enum ）型と同じようなものである。次の例では、

12data Direction = North | South | West | East
deriving (Eq,Ord,Show)
North, South, West, East の 4 つが Direction 型を構成している。
（ deriving . . .
については後述する。）
Q 3.1.1 じゃんけんの３つの手（グー (Rock)・チョキ (Scissors)・パー (Paper) ）を表すデータ型 RPS を定義せよ。
一般的には代数的データ型の構成子はパラメータを持つ。次の例は二分木を表すデータ型を定義している。

12

data Tree a = Empty | Branch (Tree a) a (Tree a)deriving (Eq, Ord, Show)

III - 1

このデータ型は Branch と Empty の 2 つの構成子を持つ。Empty は引数を取らず、それだけで二分木を構成する。Branch は 3 つのフィールド を持つ。1 番目と 3 番
目は自分自身と同じ型の二分木であり、2 番目は要素である。つまり、Branch は
次のような型を持っている。

Branch ::ここで、a はであり、ここには Integer や String など の具体化な型がはいることができる。例えば Tree Integer は要素が Integer 型であるような二分木の型である。Tree 自体は型ではなく型構成子 (type constructor) である。つまり、型パラメータを伴ってはじめて型になる。
具体的には次のような式がこの Tree 型を持つ。

1
2
3
4
5
6
7
8
9
10

tree1 :: Tree atree1 = Empty
tree2 :: Tree Integer
tree2 = Branch Empty 1 Empty
tree3 :: Tree String
tree3 = Branch (Branch Empty "a" Empty)"b" (Branch Empty "c" Empty)
tree4 :: Tree Integer
tree4 = Branch (Branch Empty 1 Empty)
2 (Branch Empty 3 (Branch Empty 4 Empty))
例えば tree4 の構造は、図で表すと次のようになる。

1

???

2 ??

?


3 ??

?

4

Tree 型に対する関数は、パターンマッチングを用いて、次のように定義することができる。
1
2
3
4
5
6
7
8
9
10

top :: Tree a -> a
top (Branch _ a _) = a
isEmpty :: Tree a -> BoolisEmpty Empty = True
isEmpty _= Falsesize :: Tree a -> Integer -- 要素数、例えば size tree4 は 4size Empty = 0
size (Branch l a r) = size l + 1 + size r
Q 3.1.2 textttRPS 型の勝ち・負け・引き分けを判定する関数 judgeRPS ::-> RPS -> Ordering を定義せよ。
ここで Ordering は次のように標準ライブラリで定義された型である。
III - 2RPS

data Ordering = LT | EQ | GT
deriving (Eq, Ord, Bounded, Enum, Read, Show)
LT が負け、GT が勝ちを表すものとする
問 3.1.3 Tree 型に対して、次のような関数を定義せよ。

depth:: Tree a -> Integer -- 深さ
preorder :: Tree a -> [a]-- 前順走査inorder:: Tree a -> [a]-- 中順走査postorder :: Tree a -> [a]-- 後順走査reflect:: Tree a -> Tree a -- 鏡像
例えば 、 1 depth tree4, 2 preorder tree4, 3 inorder tree4, 4 postorder
tree4, 5 reflect tree4 の結果はそれぞれ 、 1 3, 2 [2,1,3,4], 3 [1,2,3,4],
4 [1,4,3,2], 5 Branch (Branch (Branch Empty 4 Empty) 3 Empty) 2 (Branch
Empty 1 Empty) となる。
問 3.1.4 一般の n 分木（ 任意の個数の子を持つことができる木）を表すデータ型を定義せよ。
問 3.1.5 プログラミング言語 PL/0 (http://www.inf.ethz.ch/personal/wirth/books/AlgorighmE0) の構文木を表すデータ型を定義せよ。
（発展） フィールド ラベル C の構造体のように代数的データ型の各フィールドに名前（フィールド ラベル ）をつけることも可能である。

data C = F { f1, f2 :: Int, f3 :: Bool } deriving (Eq, Ord, Show)
この宣言は、次の宣言と同等のデータ型を定義する。

data C = F Int Int Bool deriving (Eq, Ord, Show)
さらに、フィールド ラベルは新しいデータを構築するときにも、パターンマッ
チングにも使用することが出来る。いずれもコンストラクタの後に、ブレース内に “フィールド ラベル = 式” のコンマ区切りの並びを書く。

1
2
3
4

v1 = F { f1 = 5, f2 = 12, f3 = False }foo :: C -> Int
foo (F { f1 = x, f2 = y }) = x*x + y*y
このとき foo v1 の値は 169 になる
またフィールド ラベルは、データからフィールド の値を取り出す関数として使用することが出来る。例えば 、上で定義された v1 に対して、f1 v1 の値は 5 になる。
式の後に、“フィールド ラベル = 式” のコンマ区切りの並びをブレース内に書いて、指定したフィールドの値のみを変更した新しいデータを構成するときにも使用できる。v1 { f2 = 3 } の値は F { f1 = 5, f2 = 3, f3 = False }になる。

III - 33.2

型クラスとはポリモルフィズム（多相）とは関数（ メソッド ）などがを許すことをい う。さらに 、関数など が いろいろな型の引数を許し 、し かもことを、アド ホック（ ad-hoc – その場限
りの、という意味）多相という。オブジェクト指向言語の動的束縛（ dynamic binding ）はアド ホック多相の一種である。オブジェクト指向言語では、単にポリモル
フィズムという言葉で動的束縛の意味まで含むことがある。
動的束縛と似ている概念としてオーバーローディング（ 多重定義, overloading ）がある。多重定義は一つの名前が複数の意味を持つことである。例えば C の「 + 」
オペレータは int（整数）型にも double（倍精度浮動小数点数）型にも適用できる。しかし最終的には 、適用される型によって全く異なる機械語に翻訳される。
動的束縛と異なる点は、多重定義はコンパイル（ 型チェック）時に解決されてし
まう、という点である（ つまり静的な束縛である）。実行時にオペランド の型に応じて処理を振り分けるようなことは行なわない。
多重定義もアド ホック多相の実現方法の一つである。ただし 、適用範囲はコンパイル時に型がわかる場合に限定されてしまう。
Haskell のように型推論と多相型1を許す言語では、コンパイル時に得られる型
情報では演算子の実装を決定することはできない。例えば 、次のような関数:

twice x = x + x;を定義した時、x の型が整数か実数か決定できないので、+ の実装も決定できない。
というそこで、Haskell ではアド ホック多相を可能にするために、仕組みが導入されている。

3.3 オブジェクト 指向との関係
型クラスの説明に入る前に、オブジェクト指向言語で使用される概念との関連について触れる。
オブジェクト指向を特徴づけるキーワードとして動的束縛・継承（ inheritance ）・
カプセル化（ encapsulation ）の 3 つがよく挙げられる。

Q 3.3.1 左の語句の意味と対応する右の説明を線で結べ。
動的束縛
継承
カプセル化

·
·
·

· クラスの実装の詳細を他のクラスから隠すことができること· 呼び出されるメソッドがオブジェクトの実行時の型で決まること· 上位クラスのメソッド の実装を下位クラスで再利用できること

カプセル化と継承は、ポリモルフィズムと動的束縛があってこそ意味がある概念である。ポリモルフィズムがあるから、実装の詳細を入れ替えても再コンパイル
1
アド ホックな多相に対して、型によって処理が変わらない多相のことをパラメトリック（ parametric ）な多相と言う。

III - 4

せずにコード を実行することができる。また、動的束縛があるから、継承したメ
ソッド の意味がクラスに応じて自動的に変わる。そのため、プログラミング言語の実装という観点から見れば 、ポリモルフィズム、特に動的束縛こそがオブジェ
クト指向の本質であると言っても良い。

3.4 オブジェクト 指向と代数的データ型
Haskell や ML といった関数型言語では 、複数の構成子 (constructor) からなる
(algebraic data type) を定義できる。代数的データ型を構成する各構成子を、オブジェクト指向型言語のクラスに相当すると見なせば 、関数型言語もアド ホックポリモルフィズムや動的束縛に相当する機構を持っている。関
数は、さまざ まな構成子の引数を受け取り、また呼び出されるコードがパターン
マッチングにより、オブジェクトの実行時の構成子で定まる。
オブジェクト指向言語のクラスと関数型言語の代数的データ型の違いは、拡張性の方向である。代数的データ型は、既存の構成子に新しい関数を追加していくのは可能だが 、既存の関数に新しい構成子を追加することはできない。
（ 例えば
組み込みの代数的データ型であるリスト型に新しい構成子を後から追加することはできない。）逆にクラスは既存の関数（ メソッド ）を新しいデータ型（ クラス）に定義することは可能だが、既存のデータ型（ クラス）に新しい関数（ メソッド ）を追加することはできない。
（例えば 、Java の組み込みのクラスである String ク
ラスに、新しいメソッド を後から追加することはできない。）
型クラスは、関数型言語にオブジェクト指向言語と同じ方向の拡張性（ 既存の関数に新しい型を引数として追加する）を付与する仕組み、あるいはオブジェク
ト指向言語の動的束縛を関数型言語で解釈する仕組みと考えることもできる。

3.5 Haskell の型クラス
以下では Haskell の型クラスを説明する。例として、Eq という型クラスを取り上げる。
Haskell でも C と同じように「 == 」
（ 等号）オペレータは Integer（ 整数）型にも Double（倍精度浮動小数点数）型にも適用できる。一方、関数型は比較できない。例えば (\ x -> x+x) == (\ x -> 2*x) はエラーである。Haskell は多相を許す言語であるので、例えば 、

1
2
3
4

member x []= Falsemember x (y:ys) = x==y || member x ys
subset xs ys= all (\ x -> member x ys) xsという関数 member や subset を定義すると 、member 5 [1, 4, 7] のように[Integer]（ 整数のリスト ）型の引数にも、member "Kagawa" ["Tokushima","Ehime", "Kochi"] のように [String]（ 文字列のリスト ）型の引数にも適用でIII - 5

きる。しかし 、member (\ x -> x+x) [\ x -> x+1, \ x -> 2*x] のように関数のリストに適用することはできない。
member や subset の型は、単なる a -> [a] -> Bool や [a] -> [a] -> Boolではない。それでは、member や subset はどのような型を持ち、どのように実装されているのであろうか ? Scheme のように動的に型付けされる言語では、各デー
タオブジェクトが型の情報をつねに保持しているので、実行時に型に応じて適切な関数を選択することができる。しかし 、Haskell のようにコンパイル時に型チェックを行なう言語では、実行時にはデータは型の情報を保持していないのが普通である。
Haskell では、これらの関数の型は自動的に推論される（型推論 – ただし 、その方法の詳細については本稿で取り扱う範囲を超える）。型推論の結果だけを示すと、member と subset は次のような型を持っている。

member ::subset ::こ こ で “Eq a =>” と い う部 分は 、 a と い う型 変 数が Eq と い う型の 集
まり （） に 属し て い な け れ ば い け な い 、と い う 型 に 関 す
る 制 約（ type constraint ）を 表 す。Eq と い う 型 ク ラ ス は 、==（ 等 号 ）が定 義 さ れ て い る よ うな 型 の 集 ま り の こ と で あ る 。一 般 に 型 ク ラ ス と は 、のことである。
型クラスは通常のオブジェクト指向言語でのクラス・インスタンスという言葉とは意味が異なるので注意する。通常のオブジェクト指向言語ではクラスはオブジェ
クトの集まり（つまり型）であるのに対し 、Haskell の型クラスはである。
（ Java のインタフェースの概念に似ている2 。）

3.6 クラス宣言とインスタンス宣言型クラスの定義には class というキーワード を用いる。例えば 、Eq クラスの定義は Haskell では次のように書く。
（ Prelude に定義済み。）

1
2
3

class Eq a where(==), (/=) :: a -> a -> Boola /= b = not (a == b)-- !=ではないので注意-- デフォルトの定義

これが 、「型 a が型クラス Eq に属するためには、a -> a -> Bool という型を持つ 2 つの関数 (==), (/=) を持たなければいけない」という意味になる。
そして例えば以前紹介した Direction 型が Eq クラスに属する（ Direction がである）ことを宣言するためには、instance というキー
Eq のワード を用いる。
2というよりも、順序から言えば Java のインタフェースが Haskell の型クラスに似ている、というほうが適切である。

III - 6

1
2
3
4
5
6

instance Eq Direction where
North == North = True
South == South = True
West == West = True
East == East = True_== _= False(/=) 演算子については、クラス宣言の中でデフォルトの定義が用意されているので、インスタンス宣言では定義を省略することができる。
また、Tree 型の場合（後述の deriving 節がないとき）、次のように宣言する。

1
2
3
4
5

instance Eq a => Eq (Tree a) where
Empty== Empty= TrueBranch l1 n1 r1 == Branch l2 n2 r2= l1 == l2 && n1 == n2 && r1 == r2_== _= False“Eq a =>” の部分は Tree a に等号を定義するためには、要素の型である a に等号が定義されていなければいけないという制約を表す。Tree のようにパラメーターを持つ型の場合、こういう制約が必要な場合が多い。
ほとんど の型（ 例えば リストや組）は Eq クラスに属するが 、関数型について
は、一般に 2 つの関数が等価であるかど うかを判定することは原理的に不可能なので、Eq クラスに属さない。
Q 3.6.1 組込みの Bool 型と等価なデータ型:
data MyBool = MyTrue | MyFalse
を Eq クラスのインスタンスとして宣言せよ。
（ Bool 型に対する Eq クラスのイン
スタンスは標準ライブラリ中で宣言されているので、宣言をプログラム中に書く必要はない。）

Q 3.6.2 第 3 章で定義したじゃんけん（ RPS ）型を Eq クラスのインスタンスとして宣言せよ。

III - 7

Q 3.6.3 size ::義せよa -> Int というメソッド を持つクラス Sizable クラスを定

3.7 その他の標準的な型クラス
Eq の他に実用上重要な型クラスとして、Ord, Show, Num などがある。
（ 以下の説明用コード では主要でないメソッドは省略している。）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Eq a => Ord a where-- Ord は order （ 順序）のこと(<), (<=), (>=), (>) :: a -> a -> Boolmax, min:: a -> a -> a...
class Show a where
show
...

:: a -> Stringclass (Eq a, Show a) => Num a where(+), (-), (*):: a -> a -> afromInteger:: Integer -> a...
class Num a => Fractional a where(/):: a -> a -> a...
Ord は不等号、Show は文字列への変換、Num と Fractional は四則演算のメソッ
ド を定義している型クラスである。
クラス宣言の => の左側にあるクラスは、スーパークラスと呼ばれる。
例えば 、Eq は Ord のスーパークラスである。これは、例えば Ord クラスのイ
ンスタンスになる型は、必ず Eq クラスのインスタンスでなければならない、ということを意味する。
実は、これまで触れていなかったが、1 や 3.14 などの数値リテラルは、Haskell
ではそれぞれ 、1:: (Num t) => t
3.14 :: (Fractional t) => tという型を持っている。だから、例えば 1 という数値リテラルは、Int としても、
Double としても使用できる。

III - 8

Show, Eq, Ord クラスなどに対するインスタンス宣言は 、ほとんど のデータ型で必要になり、しかも同じような定義になるので、データ型の宣言が deriving[dIráIvIN] というキーワード を持っていれば 、Haskell の処理系がこれらのインスタンス宣言を自動的に生成してくれることになっている。例えば次のように書く。
12data Tree a = Empty | Branch (Tree a) a (Tree a)deriving (Eq, Ord, Show)
これで、Tree に対して期待ど おりの ==, >, show などのメソッドが定義される。

Q 3.7.1 組込みのリスト型と等価なデータ型
data MyList a = MyNil | MyCons a (MyList a)
を、deriving を用いずに、Eq クラスと Ord クラスのインスタンスとして宣言せよ。Ord クラスのメソッドにはいわゆる辞書式の順序を用いよ。
（ クラスの定義中にデフォルトの実装が定義されているので、Eq クラスの== メ
ソッド と Ord クラスの<= メソッドだけを定義すれば 、他のメソッド の定義は自動的に生成される。）
ヒント : 次のような、リストから MyList への変換を行う関数を定義して、

toMyList :: [a] -> MyList a
toMyList []= MyNil
toMyList (x:xs) = MyCons x (toMyList xs)
いくつかのケースをテストせよ。

toMyList "abc" <= toMyList "abd"toMyList "ab" <= toMyList "abc"
toMyList "ab" <= toMyList "a"toMyList "ab" <= toMyList "ba"3.8-- True-- True-- False-- True型クラスとオブジェクト 指向言語の型システムの違い

型クラスは、Haskell にオブジェクト指向言語的な拡張性を取り入れているが 、オブジェクト指向言語の型システムで可能であることをすべて模倣できるわけではない。型システムの安全性を妥協すれば 、このような拡張はいくらでも可能だ
が、Haskell では型システムの安全性（ 型チェックを通ったプログラムは、実行時に型エラーを起こさないということ ）が優先されている。

III - 9

オブジェクト指向言語では、あるスーパークラスを継承するクラスに属するオ
ブジェクトは、一つの変数に代入したり、一つのコンテナーにまとめたりすることができる。しかし 、Haskell では、例えば Integer と Char と [Integer] はす
べて Show クラスに属するが、それらを一つのリストにまとめることはできない。
つまり、次のようなプログラムは型付けできない。

-- let impossible = [1,’a’,[1,4,7]]-in map show impossible

3.9型クラスの問題点

型推論とアド ホック多相をエレガントに両立したと言える型クラスだが 、いく
つかの問題点も残っている。
曖昧さ (ambiguity)

1
2
3
4

例えば 、次のようなクラス定義があるとする。

class Show a whereshow :: a -> Stringclass Read a whereread :: String -> a
この定義の元で、次のような関数を定義する。

foo x = show (read x)
この関数の型は、foo :: (Show a, Read a) => String -> String となる。
型変数 a の型は、=>の左辺にしか現れないので、型推論で決定できない。
（ すな
わち曖昧である。） すると次のプログラムのように、

foo x = show (read x :: Integer)a の具体的な型をユーザが明示しなければ意味が定まらなくなってしまう。
（プロ
グラムの意味が型宣言に依存することになり、気持ち悪い。）
単相性制限 (monomorphism restriction) とは、（ 大雑把に言えば ）「関数束縛でなくしかも明示的な型が与えられていない変数束縛では、=>の左辺に現れる型変数は一般化しない」という、いささか不自然な規則のことである。
例えば 、次のような関数を考える。

123

genericLength :: Num a => [b] -> agenericLength []= 0
genericLength (_:xs) = 1 + genericLength xs
genericLength 関数はライブラリ関数の length :: [b] -> Int 関数と同じ定義を持つ関数だが 、戻り値の型がより一般化されている。
この関数を利用して、次のような式を定義する。

1
2

let v = genericLength [1,2,3,4]in (v,v)
III - 10

単相性制限がなければ 、Dictionary-Passing Style 変換（ 後述）を行なうと、上の式は次のように変換される。

12\ d1 d2 -> let v’ d = genericLength’ d [1,2,3,4]in (v’ d1, v’ d2)
すると genericLength（の DPS 変換後の関数）が 2 度呼び出され 、同じ リストの長さの計算を 2 度行なってしまうという変なことが起こる。単相性制限のもとでは、次のように DPS 変換される。

1
2\ d -> let v = genericLength’ d [1,2,3,4]in (v, v)
しかし 、この場合、2 つの v の出現を別の型で使用することはできない。
わかりにくいエラーメッセージ 型クラスはエラーメッセージがわかりにくい、またはそもそもエラーにならない、という欠点がある。参考文献 [4] に多くの例が挙げられている。
例えば 、

f0 xs = map (+1) xs-- (+1) は \ x -> x+1 の意味と書くべきところを間違って、-- セクションの括弧忘れ
f0 xs = map +1 xsと定義したとする。この定義は型エラーにならず。

1
2
3

f0 :: (Num (t -> (a -> b) -> [a] -> [b]),Num ((a -> b) -> [a] -> [b])) =>t -> (a -> b) -> [a] -> [b]という型を持つと判定される。以下のような定義も型エラーとならず、変な型になってしまう。

1
2
3
4
5
6
7
8
9
10
11
12
13

-- (-1) をセクションとして使えると勘違いした。
-- f1 xs = map (\ x -> x-1) xs と書かなければならない。
f1 xs = map (-1) xs-- : 演算子の型を勘違いした。
-- f2 n = n : [4,5,6] と書くべきである。
f2 n = [n] : [4,5,6]-- Haskell では浮動少数点数リテラルを . から開始することはできない。
-- 次の . 演算子と解釈されてしまう。
-- f . g = \ x -> f (g x)-- f3 r = r * sin 0.2 と書くべきである。
f3 r = r * sin .2

Q 3.9.1 上記の f1, f2, f3 の型を確かめよ。
III - 11

3.10 Dictionary-Passing Style 変換
ここからは、Haskell が型クラスをどのように実装しているかを説明する。
（ただし 、このような実装方法が Haskell の仕様に定められているわけではない。あくまでも良く使われる実装方法の一例である。）
クラス宣言・インスタンス宣言や制約された型を持つ関数は、コンパイル時にそれらを用いない普通の関数やデータの定義に書き換えられる。
まず、クラス宣言は次のようなメソッド を要素に持つような型の宣言とアクセ
サの定義に翻訳される。

1
2
3
4
5
6
7

type Eq’ a =eq’ :: Eq’ a -> (a -> a -> Bool)eq’ = \ (e, _) -> e-- (==) に対応する
ne’ :: Eq’ a -> (a -> a -> Bool)ne’ = \ (_, n) -> n-- (/=) に対応する
この Eq’ a 型のようなオブジェクトは一般に（ method dictionary ）と呼ばれる。
インスタンス宣言は具体的な型を持つ辞書オブジェクトの定義に翻訳される。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

eqDirectionDic :: Eq’ Direction
eqDirectionDic = (eqDirection, \ a b -> not (a ‘eqDirection‘ b))
where North ‘eqDirection‘ North = True
South ‘eqDirection‘ South = True
West ‘eqDirection‘ West = True
East ‘eqDirection‘ East = True_
‘eqDirection‘ _= FalseeqTreeDic :: Eq’ a -> Eq’ (Tree a)
eqTreeDic (eqA, _) = (eqTree, \ a b -> not (eqTree a b))
where Empty ‘eqTree‘ Empty = True
Branch l1 n1 r1 ‘eqTree‘ Branch l2 n2 r2= l1 ‘eqTree‘ l2 && n1 ‘eqA‘ n2 && r1 ‘eqTree‘ r2_‘eqTree‘ _= False
そして型クラスを使っている（ . . . => . . . という型を持つ）関数の定義は、コンパイル時に次のように辞書オブジェクト（ Eq’ a 型）を追加の引数とする関数の定義に書き換えられている。つまり高階関数になる。

III - 12

1
2
3
4
5
6

member’ ::-> a -> [a] -> Bool
member’ d x []= Falsemember’ d x (y:ys) = eq’ d x y || member’ d x ys
subset’ ::-> [a] -> [a] -> Boolsubset’ d xs ys = all (\ x -> member’ d x ys) xs
これらの関数の呼出しは次のように型に応じて具体的な辞書オブジェクトを渡される形に書き換えられる。

member North [North, South, West]
North [North, South, West]7→ member’subset [North, South] [North, South, West][North, South] [North, South, West]7→ subset’
このような書き換え（ Dictionary-Passing Style 変換）は Haskell ではコンパイル中の型推論時に自動的に行なわれる。つまり、アド ホック多相の実行時のコスト
は、辞書オブジェクトの中から関数を取り出し 、それを起動するだけになる。要するに、動的束縛は高階関数で解釈できる3 。動的に（つまり実行時に）メソッド
を探しているように見えて、実際には静的に（コンパイル時に ）ほとんどの必要な処理が済んでいる。
問 3.10.1 次のように定義されている関数 lookup:

1
2
3
4
5

data Maybe a = Just a | Nothing
lookup :: Eq a => a -> [(a, b)] -> Maybe b
lookup x ((n,v):rest) = if n==x then Just v else lookup x rest
lookup x []= Nothing（ lookup は標準ライブラリに定義済みの関数である。）の Dictionary-Passing Style
変換後の形 lookupD:

lookupD :: Eq’ a -> a -> [(a, b)] -> Maybe b
を 示 せ 。例 え ば 、lookup 1 [(1,2),(4,7)]と lookupD eqIntDic 1[(1,2),(4,7)] の 値 が 、あ る い は lookup 1.1 [(1.4,0.1),(4.2,6.9)]と lookupD eqDoubleDic 1.1 [(1.4,0.1),(4.2,6.9)] の値が同じ 値になる。
（ eqIntDic, eqDoubleDic は各自で適宜定義する。）

3.11 （ 参考）他のオブジェクト 指向言語について
一般的なオブジェクト指向言語でも、たいていは “ メソッド 辞書” に対応する
データを扱うことで、動的束縛を実現している。しかし 、関数の独立した引数としてではなく、オブジェクトに付随する形になっていることが多い。つまり、各3

ただし高階関数になるので、最適化が難しくなってしまう可能性はある。

III - 13

オブジェクトがクラスに対応するデータ構造へのポインタを持っていて、クラスに対応するデータ構造が メソッド の辞書を含んでいるという場合が多い。
一方、代数的データ型の場合は、メソッド 辞書に相当するものは各関数に付随しているかたちになる。
Smalltalk のメソッド 呼出しの実装の方法は、例えば参考文献 [5] の第 6 章に説明されている。
JavaScript は、クラスではなく（ prototype ）という概念に基づくオブジェクト指向を採用している。
（ ちなみにプロトタイプ方式を最初に広めた言語は Self と言う言語である。）JavaScript のメソッド 呼出しの仕組みは [6] の第 6 章に解説がある。ただし 、最近の JavaScript はクラスも採り入れている。
Common Lisp のオブジェクト指向拡張（ CLOS ）は多重メソッド（ multi-method ）と言って、他の多くのオブジェクト指向言語と異なり、2 つ以上のパラメータの型（ クラス）によって実際に呼出すメソッド の実装を決定する仕組みを持っている。
Java では、char, int や double などのプリミティブ型に対して、他のオブジェ
クトと異なる扱いをする。これは、実行時にこれらのプリミティブ型のデータに型（ クラス）の情報を持たせることができないからである。しかし 、Scala や C#
では、プリミティブ型とクラスの区別はない。
問 3.11.1 実際のオブジェクト指向言語（ Smalltalk[5], CLOS, JavaScript[6], C++,
Java[7], Python, Ruby など ）で動的束縛や継承がど のように実装されているか調
べよ。

3.12 まとめ型クラスは、Haskell でアド ホック多相を可能にするための仕組みである。既存の関数を新しいデータ型に定義するための仕組みでもある。コンパイル時に高階関数への変換が行なわれるので、実行時のコストはほとんどかからない。しかし 、わかりにくいエラーメッセージなどの問題は残っている。

3.13 さらに詳し く知りたい人のために . . .
文献 [1] は、型クラスのアイデアを最初に紹介した論文である。文献 [2] は、現在の Haskell の型クラスを詳しく説明している。文献 [3] は、Haskell の（ 型クラスに関する部分を含む）型推論を、具体的に Haskell のプログラムを用いて説明している。文献 [4] は、型クラスのエラーメッセージの問題点と改良法について詳しく述べている。

この章の参考文献[1] Philip Wadler and Stephen Blott 「 How to make ad-hoc polymorphism less adhoc 」1988 年 10 月
III - 14

Conference Record of the Sixteenth Annual ACM Symposium on Principles ofProgramming Languages, pp. 60–73[2] Cordelia Hall, Kevin Hammond, Simon Peyton Jones and Philip Wadler「 Type Classes in Haskell 」 1996 年
ACM Transactions on Programming Languages and Systems 18 巻 2 号, pp. 109–
138
[3] Mark P. Jones 「 Typing Haskell in Haskell 」 2000 年 11 月
http://www.cse.ogi.edu/∼mpj/thih/[4] Bastiaan Heeren and Jurriaan Hage 「 Type Class Directives 」 2005 年 1 月
Seventh International Symposium on Practical Aspects of Declarative Languages(LNCS 3350), pp.253–267[5] Mark Guzdial and Kim Rose 編、 軋音組 訳「 Squeak 入門 過去から来た未来のプログラミング環境」 2003 年 3 月 星雲社[6] 久野 靖 「入門 JavaScript 」 2001 年 8 月 ASCII[7] Tim Lindholm and Frank Yellin 著、村上 雅章 訳
「 Java 仮想マシン仕様 第 2 版」 2001 年 5 月 ピアソン・エデュケーション

III - 15