Writing pop and push functions for Haskell stack

Question

Hi I'm trying to create pop and push functions for a Haskell stack defined like this :

data mystack = Empty | Elem Char mystack deriving Show

If I didn't have this definition restriction I would do push like this

push x mystack = (x:mystack)

and pop like this

pop mystack = head mystack

But with this restriction I don't know how to implement these functions. Can you give me some hint how to do these please? I even couldn't write a Stack type with that description myself.

Answer 1

Hint: here is how you might implement your stack operations using the built-in list:

push :: a -> [a] -> ((),[a])  -- return a tuple containing a 'nothing' and a new stack
push elem stack = ((), (:) elem stack)

pop :: [a] -> (a, [a])  -- return a tuple containing the popped element and the new stack
pop [] = error "Can't pop from an empty stack!"
pop ((:) x stack) = (x, stack)

(:) x xs is an alternative way of writing x:xs.

To do this on your own MyStack type, note that your Empty actually works just like [], and Elem is equivalent to (:). I won't give you the code to do this outright, because figuring it out for yourself is half the fun!