代数的データ型その10

Haskell

再帰的な型です。

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

上記のように自分自身を型の宣言に使えます。と言うわけで本に書いてあった例を基にして、サンプルを作ってみました。

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

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

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

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

stk1 = Empty
stk2 = Push 1 (Empty)
stk3 = Push 2 (Push 1 (Empty))

main = do print $ isEmpty stk1             -- True
          print $ isEmpty stk2             -- False
          print $ isEmpty stk3             -- False
          print $ top stk2                 -- 1
          print $ top stk3                 -- 2
          print $ top $ pop stk3           -- 1
          print $ isEmpty $ pop stk3       -- False
          print $ isEmpty $ pop $ pop stk3 -- True

popしてもスタックの中身が変わらないというは違和感があります。