--
-- Abstract Data Types
--

{-- A Stack ADT
data Stack a

newStack :: Stack a
push :: Stack a -> a -> Stack a 
pop :: Stack a -> (Stack a,a)
isEmpty :: Stack a -> Bool

---}

---if you export the constructors, it is no longer abstract:
---module StackADT (Stack(Empty,Stack),newStack,push,pop,isEmpty) where

module StackADT (Stack,newStack,push,pop,isEmpty) where

data Stack a  = Empty | Stack a (Stack a)

newStack :: Stack a
push :: Stack a -> a -> Stack a 
pop :: Stack a -> (Stack a,a)
isEmpty :: Stack a -> Bool

newStack        = Empty
push s e        = Stack e s
pop (Stack e s) = (s,e)
isEmpty Empty   = True
isEmpty _       = False

instance Eq a => Eq (Stack a) where
    Empty         == Empty         =  True
    (Stack e1 s1) == (Stack e2 s2) =  (e1 == e2) && (s1 == s2)
    _             == _             =  False

instance Show a => Show (Stack a)  where 
    show Empty       = "Empty"
    show (Stack e s) = show e ++ "|" ++ show s

instance Functor Stack where
    fmap f Empty       = Empty
    fmap f (Stack e s) = Stack (f e) (fmap f s)