[Haskell] Stack

1. 列表表示

module Stack(Stack,push,pop,top,emptyStack,stackEmpty) where

newtype Stack a  = Stk [a]

push :: a -> Stack a -> Stack a
push x (Stk xs) = Stk (x:xs)

pop :: Stack a -> Stack a 
pop (Stk []) = error "pop from an empty stack"
pop (Stk (_:xs)) = Stk xs

top :: Stack a -> a 
top (Stk []) = error "top from an empty stack"
top (Stk (x:_)) = x 

emptyStack :: Stack a
emptyStack = Stk [] 

stackEmpty :: Stack a -> Bool
stackEmpty (Stk []) = True
stackEmpty (Stk _) = False

2. 自定义类型表示

module Stack(Stack,push,pop,top,emptyStack,stackEmpty) where

data Stack a  = EmptyStack | Stk a (Stack a)

push :: a -> Stack a -> Stack a
push x s = Stk x s

pop :: Stack a -> Stack a 
pop EmptyStack = error "pop from an empty stack"
pop (Stk _ s) = s

top :: Stack a -> a 
top EmptyStack = error "top from an empty stack"
top (Stk x _) = x 

emptyStack :: Stack a
emptyStack = EmptyStack

stackEmpty :: Stack a -> Bool
stackEmpty EmptyStack = True
stackEmpty _ = False

参考

Algorithms: A Functional Programming Approach