Kiterminal's Blog

newtype Stack a = Stk [a] deriving Show
 
push x (Stk xs) = Stk (x:xs)
 
pop (Stk []) = error "pop from an empty stack"
pop (Stk (_:xs)) = Stk xs
 
top (Stk []) = error "top from an empty stack"
top (Stk (x:_)) = x
 
emptyStack = Stk []
 
stackEmpty (Stk []) = True
stackEmpty (Stk _ ) = False

$ hugs Stacks.hs
Main> push 5 (push 3 (push 1 emptyStack))
Stk [5,3,1]
Main> top (push 5 (push 3 (push 1 emptyStack)))
5
Main> pop (push 5 (push 3 (push 1 emptyStack)))
Stk [3,1]

newtype Queue q = Q([q], [q]) deriving Show
 
queueEmpty (Q ([], [])) = True
queueEmpty _ = False
 
emptyQueue = Q ([], [])
 
enqueue x (Q ([], [])) = Q ([x], [])
enqueue y (Q (xs, ys)) = Q (xs, y:ys)
 
dequeue (Q ([], [])) = error "dequeue: empty queue"
dequeue (Q ([], ys)) = Q (tail (reverse ys), [])
dequeue (Q (x:xs, ys)) = Q (xs, ys)
 
front (Q ([], [])) = error "front: empty queue"
front (Q ([], ys)) = last ys
front (Q (x:xs, ys)) = x

$ hugs Queues.hs
Main> enqueue 5 (enqueue 3 (enqueue 1 emptyQueue))
Q ([1],[5,3])
Main> front (enqueue 5 (enqueue 3 (enqueue 1 emptyQueue)))
1
Main> dequeue (enqueue 5 (enqueue 3 (enqueue 1 emptyQueue)))
Q ([],[5,3])