import Control.Applicative
import Control.Monad
import Data.Monoid

data List a = Nil | (:::) a (List a) deriving (Show, Read)
infixr 5 :::

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

instance Monoid (List a) where
	mempty = Nil
	(x ::: xs) `mappend` b = x ::: (xs `mappend` b)
	Nil `mappend` b = b

instance Applicative List where
	pure = return
	(<*>) = ap

instance Monad List where
	return x = x ::: Nil
	Nil >>= _ = Nil
	(x ::: xs) >>= f = f x `mappend` (xs >>= f)

instance MonadPlus List where
	mzero = mempty
	mplus = mappend

instance Alternative List where
	empty = mempty
	(<|>) = mappend