bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

Haskellの真髄に迫る: 一般化代数的データ(1)

1.代数的データ型の「代数」は何を意味するのか

代数的データ型という言葉はHaskellを始めた人にとってはなじめない言葉だ。代数という言葉の意味は、そのままとれば、数を文字で置き換えるということになる。代数的データ型を用いて整数(Int)を定義しようとすれば、次のようになる。

data Int = -2147483648 | -2147483647 | ... | -1 | 0 | 1 | ... | 2147483647

代数的データ型とは-2147483648から2147483647までの数をIntという文字で置き換えたということであろうか?

中学時代の頃を思い出すと、代数は方程式を表していたように思う。即ち、等号を用いて表す対象間の関係である。例えば、\( x^2 + 3x + 2 = 0 \)である。「すごいHaskell楽しく学ぼう!」によれば、代数的データ型を用いてリストは次のように定義できる。

infixr 5 :-:
data List a = Empty | a :-: (List a) deriving (Show, Read, Eq, Ord)

ここで、infixは中置関数を定義するもので、rがつくと右結合を示す。よく見かける四則演算などの中置関数は左結合なので、読む方向に操作していくが、右結合はひっくり返して操作する感じになる。また、中置関数を定義するときはこーろんで始めないといけない。
リストはEmptyであるか、あるいは、型引数aとList aを中置関数:-:でつなげたものである。
この定義を用いてリストをいくつか作ってみる。
f:id:bitterharvest:20140908110910p:plain
最初は、Emptyがリストに属しているかどうかを確かめたものである。次は、aをEmptyとし、後の操作で利用できるようにしている。次は、数とEmptyを接続してリストとしたもの。さらに、文字と数とEmptyを接続したらどのようなことが起こるかを示したもの。もちろんリストにはならない。この辺は、Haskellの強靭さを示すものである。最後は、二つの数とEmptyを接続してリストとしたもの。定義した中置関数が右結合であることを示している。

ここで定義した中置関数:-:は四則演算などと同じように演算子とみなしてよいので、上の定義は、リストはa :-: (List a)という式(あるいはEmpty)と等価であるといっている。中学校で習った方程式と感じは似てきたが、これは表面的なことのように思える。代数的データ型には、もっと深い意味がありそうなので、その神髄を探っていくことにする。

ところで、リストの話が出てきたので、これは後でも用いるので、もう少し説明を加えておく。「すごいHaskell楽しく学ぼう!」によれば、リストは次のように定義している。

data List a = Empty | Cons a (List a)  deriving (Show, Read, Eq, Ord)

ここで、Listは型コンストラクタと呼ばれ、aは型引数、EmptyとConsは値コンストラクタと呼ばれている。型コンストラクタは、型名がListである型を作り出すことを宣言している。aはListを作り出す引数であるが、その型は定義されていない。その型はリストを作成するときに定義される。例えば、文字のリストであれば、aの型はCharとなるし、整数のリストであれば、aの型はIntとなる。いわゆる、多相型と呼ばれるものである。

上記の定義は、Lispの経験がある人であれば割合と受け入れやすいと思うが、そうでない人にとっては最初は分かりにくいかもしれない。同じ本にレコード構文での定義が載っているので、これも併せて紹介しておく。

data List a = Empty | Cons {listhead :: a, listTail :: List a}  deriving (Show, Read, Eq, Ord)

これだと、データベースの分野から入ってきた人も分かりやすいのでないかはと思う。

さて、上述の定義は一般化代数的データ型(Generalized algebraic data type、略してGADT)を用いると次のように変えられる。

{-# LANGUAGE GADTs #-}
data List a where
  Empty :: List a
  Cons  :: a -> List a -> List a
  deriving (Show, Read, Eq, Ord)

Consの定義は、次のように読める。値コンストラクタConsは、aと(List a)を入力とし、(List a)を出力とする関数である。即ち、\( y = f(a,x) \)。ここで、 \( f= Cons\)かつ\(x,y \in List \)である。このように、一般化するとデータ型が関数のように定義されるので、代数的な要素がさらに強くなることがわかる。
この定義を用いての実行例を次に示す。
f:id:bitterharvest:20140908125817p:plain
実行例では差は生じない。
しかし、一般化することで大きな利益が生じるが、この話を次にする。