import Control.Monad

data List a = Nil
            | Cons a (List a)
            deriving (Show, Eq)

instance Monoid (List a) where
    mempty = Nil

    mappend xs  Nil = xs
    mappend Nil ys  = ys
    mappend xs  ys  = let go Nil         l = l
                          go (Cons x xs) l = go xs (Cons x l)
                      in  go (reverse' xs) ys

reverse' :: List a -> List a
reverse' xs = let go Nil         l = l
                  go (Cons x xs) l = go xs (Cons x l)
              in  go xs Nil

instance Functor List where
    fmap _ Nil         = Nil
    fmap f (Cons x xs) = Cons (f x) (fmap f xs)

instance Applicative List where
    pure x = Cons x Nil

    Nil       <*> _   = Nil
    _         <*> Nil = Nil
    Cons f fs <*> xs  = mappend (fmap f xs) (fs <*> xs)

instance Monad List where
    Nil       >>= f = Nil
    Cons x xs >>= f = mappend (f x) (xs >>= f)