第10章 型とクラスの定義 #2

前回の日記でdataによる型定義を学んだけど、これ、もっと掘り下げておくべきだったな。

引数なしのデータコンストラクタだと列挙型みたいなもの。これはOK。たとえば、Bool型の要素がTrueとFalse、といった形でこれまでも登場している。 でも引数ありのデータコンストラクタを持つ型は、これまでになかったものだ。これはCで言えば構造体だし、オブジェクト指向言語でいえばオブジェクトにあたるのだけど、以下が違う。

• フィールドには名前がいらない。
• 名前のないフィールドを参照するときはパターンマッチ（順序で区別する）。

この理解は正しいかな？と思いながらググったら、こんなこともわかった。

• データコンストラクタのパターンマッチは、リストのパターンマッチという形ですでに登場していた
• フィールドには名前をつけることもできる。

ふむ。教科書にはそこまで書いてないから、先取りしたことになるだろうか。

10.3 再帰型

ここのコード写経ではデータコンストラクタのパターンマッチがたくさん登場する。

まずは、ペアノの公理みたいな自然数定義（ゼロは自然数！）。 教科書ではn+kパターンで書かれていた部分を書き換えてみながら。 （ちなみに、NatをShowクラスのインスタンスにしていないので、hugsやghicでNatを評価するとエラーになってしまう。）

-- rec (Peano axioms)
data Nat = Zero | Succ Nat

nat2int          :: Nat -> Int
nat2int Zero     =  0
nat2int (Succ n) =  1 + nat2int n

int2nat   :: Int -> Nat
int2nat 0 =  Zero
int2nat n =  Succ (int2nat (n-1))
-- n + k pattern
-- int2nat (n + 1) =  Succ (int2nat n)

add            :: Nat -> Nat -> Nat
add Zero n     =  n
add (Succ m) n =  Succ (add m n)

続いて、リスト（コンスセルのリスト）を自分定義。

-- rec (List)
data List a = Nil | Cons a (List a)

len             :: List a -> Int
len Nil         =  0
len (Cons _ xs) =  1 + len xs

最後に、二分木。なお、occurs'関数は二分探索木用の定義。

-- rec (Binary Tree)
data Tree = Leaf Int | Node Tree Int Tree

t :: Tree
t =  Node (Node (Leaf 1) 3 (Leaf 4)) 5 (Node (Leaf 6) 7 (Leaf 9))

occurs                :: Int -> Tree -> Bool
occurs m (Leaf n)     =  m == n
occurs m (Node l n r) =  m == n || occurs m l || occurs m r

flatten              :: Tree -> [Int]
flatten (Leaf n)     =  [n]
flatten (Node l n r) =  flatten l ++ [n] ++ flatten r

occurs' :: Int -> Tree -> Bool
occurs' m (Leaf n) =  m == n
occurs' m (Node l n r)
  | m == n    = True
  | m < n     = occurs' m l
  | otherwise = occurs' m r

おまけで、木構造の定義のバリエーション。

-- data Tree a = Leaf a | Node (Tree a) (Tree a)
-- data Tree a = Leaf | Node (Tree a) a (Tree a)
-- data Tree a b = Leaf a | Node (Tree a b) b (Tree a b)
-- data Tree a = Node a [Tree a]