Concurrent Crean 1部3章続き

代数データ型

:: Day = Mon | Tue | Wed | Thu | Fri | Sat | Sun

datatype。列挙する。

多相ツリー型

:: Tree a = Node a (Tree a) (Tree a)
          | Leaf

ツリーデータ

Node 7 (Node 3 (Node 5 Leaf
                       Leaf
               )
               Leaf
       )
       Leaf

パターン形式の関数定義

sizeT :: Tree a -> Int
sizeT Leaf         = 0
sizeT (Node x p q) = 1 + sizeT p + sizeT q

クラスEq、Ord

要素が昇順になっているということを想定できるならば、幾分か便利になる。求められている要素を渡すと、探索を止めることができる。結果として、その要素は比較可能であるだけでなく（クラスEq）、整列可能でなければならない（クラスOrd）。

elem' :: a [a] -> Bool | Eq, Ord a
elem' e []     = False
elem' e [x:xs] = e == x || (e > x && elem' e xs)

つまりEqは==、Ordは>が使えるということ。

抽象データ型

ここからはモジュール。

definition module stack

:: Stack a

Empty   ::   (Stack a)
isEmpty ::   (Stack a) -> Bool
Top     ::   (Stack a) -> a
Push    :: a (Stack a) -> Stack a
Pop     ::   (Stack a) -> Stack a

stackモジュールのdefinitionには、型名とそれを使う関数の型だけを列挙する。

implementation module stack

:: Stack a :== [a]

Empty :: (Stack a)
Empty = []

isEmpty :: (Stack a) -> Bool
isEmpty [] = True
isEmpty s  = False

Top :: (Stack a) -> a
Top [e:s] = e

Push :: a (Stack a) -> Stack a
Push e s = [e:s]

Pop :: (Stack a) -> Stack a
Pop [e:s] = s

implementationで実態を書く。