前回の日記で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]
