--
-- Abstract Data Types
--

-- A Stack ADT
data Stack a  = Empty | Stack a (Stack a)

newStack :: Stack a
newStack = Empty
push :: Stack a -> a -> Stack a 
push s e = Stack e s
pop :: Stack a -> (Stack a,a)
pop (Stack e s) = (s,e)
isEmpty :: Stack a -> Bool
isEmpty Empty = True
isEmpty (Stack _ _) = 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)

{-- Test it with:
let s1 = push (push newStack 1) 2
s1                     -- displays 2|1|Empty
let (s2,e) = pop s1
e
s2
s1 == s2
let (s3,_)= pop s2
s3 == newStack
fmap (\x -> x*x) s1    -- displays 4|1|Empty
fmap (\x -> x > 1) s1  -- displays True|False|Empty
fmap (\x -> x > 1) (fmap  (\x -> x*x) s1)  -- is equivalent to:
fmap ((\x -> x > 1) . (\x -> x*x)) s1
--}