FP Laboratory 10

Abstract data types

• Create an implementation of the abstract data type Stack with following functions:

push :: a -> Stack a -> Stack a
pop :: Stack a -> Stack a
top :: Stack a -> a
isEmpty :: Stack a ->Bool

• Create an implementation of the abstract data type Queue with following functions:

isEmpty :: Queue a -> Bool
addQ :: a -> Queue a -> Queue a
remQ :: Queue q -> (a, Queue a)

module Queue(Queue, emptyQ, isEmptyQ, addQ, remQ) where
    data Queue a = Qu [a]

    emptyQ :: Queue a
    emptyQ = Qu []
    
    isEmptyQ :: Queue a -> Bool
    isEmptyQ (Qu q) = null q
    
    addQ :: a -> Queue a -> Queue a
    addQ x (Qu xs) = Qu (xs++[x])
    
    remQ :: Queue a -> (a,Queue a)
    remQ q@(Qu xs) | not (isEmptyQ q) = (head xs, Qu (tail xs))
                   | otherwise        = error "remQ"