Monads for free!

Free.hs

module Free where 


data Term f a = Pure a 
              | Impure (f (Term f a))

instance Functor f => Functor (Term f) where
    fmap f (Pure a) = Pure (f a)
    fmap f (Impure g) = Impure (fmap (fmap f) g)

instance Functor f => Applicative (Term f) where 
    pure = Pure

    ff <*> Pure a = fmap (\f -> f a) ff
    Pure f <*> Impure g = Impure (fmap (fmap f) g)
    Impure ff <*>  g = Impure (fmap (<*>g) ff)


instance Functor f => Monad (Term f) where 
    return = pure 

    Pure a >>= f = f a
    Impure fa >>= f = Impure (fmap (>>=f) fa)