FP Laboratory 10

From Marek Běhálek Wiki
Revision as of 12:35, 14 November 2022 by Beh01 (talk | contribs)
Jump to navigation Jump to search

Abstract data types

Video logo.png
  • 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
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
  • Create an implementation of the abstract data type Queue with following functions:
isEmpty :: Queue a -> Bool
addQ :: a -> Queue a -> Queue a
remQ :: Queue a -> (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"