型と型クラス

9.2 代数的データ型

再帰的な型について

う〜ん、ちょっと難しい。。。一回読んだだけでは理解出来なかった。
細かく読み解いていこう。
本文中にあった例をそのまま使わせていただくと、

data Stack a = Empty | Push a (Stack a)

という型宣言。

data Stack a =

の部分は問題ないです。
「Stack」は型コンストラクタで、「a」はその引数(型！)。
問題は後半部です。

Empty | Push a (Stack a)

「Empty」は何？ということなんだけど、Preludeの中を探しても、そんな定義見つからない。
そうなんです、「Empty」は引数なしのデータコンストラクタなんです。

「|」は先日勉強した共用体スタイルの型宣言演算子(っていうの？)ですね。

そして一番問題なのが、「Push a (Stack a)」です。
この中を分解してみます。
前半部分の「Push a」。これはデータコンストラクタですね。
引数に型コンストラクタStackの引数を使っています。つまり「a」は任意の型なわけです。
後半部分の「(Stack a)」。これはデータコンストラクタ「Push」の第二引数です。
つまり、データコンストラクタ「Push」の第二引数には、(Stack a)という型を指定出来るのです。

う〜ん、ここ！ここが分かりにくいんです。
本当に簡易的な感じで書いてみると…

Stack a = Empty | Push a (Stack a)
Stack a = Empty | Push a (Empty | Push a (Stack a)
Stack a = Empty | Push a (Empty | Push a (Empty | Push a (Stack a)))
Stack a = Empty | Push a (Empty | Push a (Empty | Push a (Empty | Push a (Stack a))))
-- 続く続く…

となるわけです。じゃぁ、この定義、いつまで続くのか？
それは「Stack a」が「Empty」になるまで続きます。

なんか見たことあるなぁ、と思います。
そうです、map関数の定義とまるっきり同じノリなんですよね。
map関数の定義はこんな感じでした。

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f (xs)

map関数の第二引数が「[]」になるまで展開されるわけですね。

最後に(Stack a)型を使っていろいろ遊んでみました。

main = do print $ isEmpty st1
          print $ top st1
          print $ isEmpty $ pop $ pop $ pop $ pop st1

data Stack a = Empty | Push a (Stack a)

isEmpty :: Stack a -> Bool
isEmpty Empty      = True
isEmpty (Push _ _) = False

top :: Stack a -> a
-- top Empty      = 
top (Push x _) = x

pop :: Stack a -> Stack a
pop (Push _ stk) = stk

st1 :: Stack Char
st1 = Push 'd' (Push 'c' (Push 'b' (Push 'a' (Empty))))

% ghc -o example3 example3.hs
% ./example3                 
False
'd'
True

う〜ん、top関数は引数がEmptyの時、何を返すべきなんだろう？
a型の何かを返さなきゃいけないんだけど…。
上の例ではパターンマッチングしてないので、ghcのオプション「-W」は外してます。。。