CSE 130 
Sample Solutions: (Small) Group Project 2


-- PROBLEM 1

-- Part a: SPECIFICATION (signature) 

module Queue (newQ, emptyQ, enQ, deQ, headQ)
where


newQ 	:: Queue a
emptyQ	:: Queue a -> Bool
enQ	:: a -> Queue a -> Queue a
deQ	:: Queue a -> Queue a
headQ 	:: Queue a -> a


-- SPECIFCATION (constraints; partial solution)

... assume the queue Q corresponds to a sequence 

 -- enQ --> [e_1,e_2, ..., e_n] -- deQ -->

headQ  Q will lead e_n

deQ Q will lead [e_1,e_2, ..., e_{n-1}]

enQ x Q will lead [x, e_1,e_2, ..., e_n]

...


-- IMPLEMENTATION (concrete data type)

data Queue a = EmptyQueue | QueueC a (Queue a) deriving Show


-- IMPLEMENTATION ("code")

newQ = EmptyQueue

emptyQ  EmptyQueue = True
emptyQ  a          = False

enQ x EmptyQueue = QueueC x EmptyQueue
enQ x y          = shift y (QueueC x EmptyQueue)

shift :: Queue a -> Queue a -> Queue a
shift (QueueC a EmptyQueue) b  = QueueC a b
shift (QueueC a b) c           = QueueC a (shift b c)


deQ EmptyQueue   = error "ERROR: cannot deQ an empty queue!"
deQ (QueueC a b) = b

headQ EmptyQueue   = error "ERROR: cannot get head of an empty queue!"
headQ (QueueC a b) = a




-- showQueue is a nicer way to display the contents of a queue.
showQueue :: (Show a) => Queue a -> String
showQueue EmptyQueue = ""
showQueue (QueueC a EmptyQueue) = show a
showQueue (QueueC a b) = show a ++ ", " ++ showQueue b





{- Problem 2 a:

this is only a sketch of the solution. The complete solution needs to
include the specification!

-} 



-- good old polymorphic stack:

data Stack a	= MTstack | Add a (Stack a)
		deriving Show

create		:: Stack a
create		= MTstack

push		:: a -> Stack a -> Stack a
push x s	= Add x s 


pop		:: Stack a -> (a, Stack a)
pop (Add x s)	= (x, s)
pop MTstack	= error "can't pop from empty stack"


-- CHECK THIS OUT:
-- pushElements takes a stack and a list of elements 
-- and pushes those elements on the stack, returning
-- the new stack!!

pushElements		:: Stack a -> [a] -> Stack a 
pushElements s []	= s
pushElements s (x:xs)	= pushElements (push x s) xs 


-- popElements takes a stack on pops off its elements
-- into a list!
popElements		:: Stack a -> [a]
popElements MTstack	= []
popElements (Add x s)	= x : (popElements s)

-- EXCERCISE: do popElements using pop and guards intead of 
-- using the data constructor "Add" directly ...




-- and finally: this is what it should look like:
-- to reverse a list, you push the "xs" list onto
-- the empty stack (=create returns the empty stack) 
-- and then the elements are popped off
reverselist xs		= popElements (pushElements create xs)


-- same as before but note the "." for function composition
-- and the missing "xs" 
reverselist'		= popElements . (pushElements create)