Writing pop and push functions for the Haskell stack

Question

Hey. I am trying to create pop and push functions for a Haskell stack defined as follows:

data mystack = Empty | Elem Char mystack deriving Show 

If I did not have this restriction of definition, I would make it as if

 push x mystack = (x:mystack) 

and pop like that

 pop mystack = head mystack 

But with this limitation, I do not know how to implement these functions. Can you give me a hint how to do this, please? I could not even write a stack type with this description.

Answer 1

Hint: here's how to implement 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 to write x:xs .

To do this in the MyStack native type, note that your Empty works the same as [] , and Elem equivalent (:) . I will not give you the code to do it directly, because figuring it out for myself is half the fun!