(代数的)データ型を定義する

date:	2012/12/14

1. 概要
2. (代数的)データ型について
3. まとめ
4. コード

1. 概要

データ型を定義してみる
自動導出を使って、データ型を型クラスのインスタンスにしてみる
自然数, 整数を定義する

2. (代数的)データ型について

2.1. 型クラスと型

型クラスというのは、関数のあつまりを指定しています。
型は、(いくつかの)型クラスの指定する関数を具体的に実装したものです。
ある型がある型クラスのインスタンスであるというのは、 型クラスの要求するすべての関数を型が実装していること 、としましょう。

2.2. データ型をつくる

データ型を定義してみましょう。

例えば、次の形式で定義できます。

data (TypeName) = (TypeConstructer) [ | (TypeConstructer) | ... ] [deriving (TypeClass[,...])]

TypeName, TypeConstructer, TypeClass を表す文字列は、大文字からはじめる必要があります。

例えば、以下のようにしてデータ型をつくることができます。

data Weekday = Sun | Mon | Tue | Wed | Thu | Fri | Sat

これで Weekday という型をつくることができました。
この型は、Sun, Mon, ...といったものを含みます。それぞれWeekday型の値を返す関数(Haskell では引数がなくても関数)です。
このようなdata型を定義する、値を返す関数は値コンストラクタと呼ばれます。

さて、Int 型が10, 40, などといった数を含むのと同様に、Weekdayを定義できました。

一旦データ型が定義されれば、holiday :: Weekday -> Bool のように、Weekdayからの関数などを自由に書くことができるようになります。

-- 毎日休みだとうれしい
holiday :: Weekday -> Bool
holiday _ = True

2.3. 型クラスのインスタンスへ

先ほど、作った Weekday を実際に使ってみると、1つ困ることがあるかもしれません。
例えば、 ghci などで、 Sun を表示しようとすると、エラーが出るでしょう。
なぜならば、今のところ、Sun を文字列として表示する方法を決めていないからです。
ここでは、 Weekday 型を Show 型クラスのインスタンスにすることで、表示できるようにしましょう。(型クラスというのは、関数の集まりを決めているものでした。)

data Weekday = Sun | Mon | Tue | Wed | Thu | Fri | Sat deriving (Show)

最後に、 deriving (Show) というものが追加されました！
これは、自動導出と呼ばれる仕組みで、 ある型を特定の型クラスのインスタンスにする宣言を自動導出する (つまりインスタンスにするために必要な関数も勝手に定義してくれる)というものです。
今の場合、 Weekday 型が Show 型クラスのインスタンスになりました。

Show 型クラスは次の3つの関数の実装を要求します。

showsPrec :: Int -> a -> ShowS
show :: a -> String
showList :: [a] -> ShowS

実際に表示される際には、この中の show メソッドを使って、Sun を表示します。

(show Sun) が文字列になるのでそれを表示するわけです。

2.4. 型クラスの例

自動導出をするときによく使われる型クラスの例を挙げておきます。

型クラスの名前でなんとなくどういうクラスかわかるだろうと期待して、説明は省略します。

Eq 型クラス
Ord 型クラス
Show 型クラス
Read 型クラス
Enum 型クラス

2.5. 再帰的なデータ型

よく使う型として、リスト型があります。
型 a に対して、 [a] という型が定義されているはずです。
これがどのように定義されているか見てみます。(自動導出は省略しています。)

data [] a = [] | a : [a]

左辺:	data [] a

* a は型引数と呼ばれます。
* [] は型引数を取って、型をつくります。型コンストラクタと呼ばれます。
* a が Int や Boolとしてみれば、[Int],[Bool] などが宣言されていることがわかります。

[a] というのは、 [] a の略記です。

右辺:	[] \| a : [a]

* [] は空の配列を表します。

* [a] が右辺にも登場しています。これは再帰的なデータ型と呼ばれます。

* : は a, [a] という2つの引数をとっています。これは値コンストラクタと呼ぶのでした。

(:) :: a -> [a] -> [a] となっています。

リストの例をあげれば、 1:[2:[3:[]]] はリストです。これを普段は、[1, 2, 3]と略記しています。

というわけで、リストの定義を見ることで、型コンストラクタ, 値コンストラクタ, 再帰的なデータ型を知ることができました。

3. まとめ

途中にコードを書くと長くなってしまうので、先にまとめをしておきます。

以上のようにして、自分独自のデータ型を作ることができます。

ここで触れませんでしたが、型クラスのインスタンスにする方法は、自動導出だけではありません。また、型クラス自体も定義することができますが、それについては、またそのうち。

4. コード

最後に自然数と整数を定義してみましょう。

方針としては、自然数を再帰的なデータ型で定義しておいて、整数は自然数の定義から自然に拡張する、というものです。

-- 自然数の構成
data Nat = Zero | Succ Nat deriving (Eq, Ord, Show)
-- 足し算と掛け算
add :: Nat -> Nat -> Nat
m `add` Zero     = m
m `add` (Succ x) = Succ (m `add` x)
prod :: Nat -> Nat -> Nat
m `prod` Zero     = Zero
m `prod` (Succ x) = (m `prod` x) `add` m
-- 自然数の中で引き算した気になる
-- x - y で、yが大きいときは 0にしてしまう
natSubtract :: Nat -> Nat -> Nat
natSubtract x y
  | x > y     = f x y Zero
  | otherwise = Zero
    where f x y m = if x == y then m else f x (Succ y) (Succ m)

-- 整数のこと (Zahl なので。)
-- type は 型に別名をつける。(新しい型を定義しているわけではない)
type Zah = (Nat, Nat)
normarilze :: Zah -> Zah
normarilze (x, y)
  | x == Zero || y == Zero = (x, y)
  | x == y = (Zero, Zero)
  | x > y  = (natSubtract x y, Zero)
  | x < y  = (Zero, natSubtract y x)
-- マイナス倍
negateZah :: Zah -> Zah
negateZah (x, y) = (y, x)
-- 絶対値
abs :: Zah -> Nat
abs (x, y) = if z == Zero then w else z
             where (z, w) = normarilze (x, y)
-- 足し算と掛け算
addZah :: Zah -> Zah -> Zah
addZah (x, y) (z, w)  = normarilze (x `add` z, y `add` w)
prodZah :: Zah -> Zah -> Zah
prodZah (x, y) (z, w) = normarilze ((x `prod` z) `add` (y `prod` w)
                                    , (y `prod` z) `add` (x `prod` w))
-- 引き算
subtractZah :: Zah -> Zah -> Zah
subtractZah x y = addZah x (negateZah y)

Study Haskell