FP Laboratory 10/cs

Abstraktní datové typy

• Implementujte abstraktní datový typ Stack s následujícími funkcemi:

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

module Stack(Stack, emptyS, push, pop, top, isEmpty) where
  data Stack a = Stack [a] deriving Show

  emptyS :: Stack a
  emptyS = Stack []

  push :: a -> Stack a -> Stack a
  push x (Stack y) = Stack (x:y)
  
  pop :: Stack a -> Stack a
  pop (Stack (_:xs)) = Stack xs

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

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

• Implementujte abstraktní datový typ Fronta s následujícími funkcemi:

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] deriving Show

    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"