5.6. Implementation of basic functions

Below are the implementations of the basic functions emptyStack, push, pop, and isEmpty, along with their type sigs. These functions are the necessary "kernel" of a stack implementation.

These functions use the concrete representation. That is, we know that the stack is really made out of a list and so we use list functions.

In this case "s" represents the list that the stack is built on.

Remember, MakeStack was defined above in the type declaration. The function null returns true if the given list is empty.

emptyStack :: Stack a
emptyStack = MakeStack []

push :: Stack a -> a -> Stack a
push (MakeStack s) element = MakeStack (element:s)

isEmpty :: Stack a -> Bool
isEmpty (MakeStack s) = null s

pop :: Stack a -> (a, Stack a)
pop (MakeStack (h:t)) = (h, MakeStack t)
pop (MakeStack []) = error "Attempt to pop an empty stack."

Can anyone tell me the type of null and (:)