[Haskell] Stack
2017-03-27 本文已影响61人
何幻
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
