How to show that a monad is a functor and an applicative functor?

Question

Monads are known to be theoretically a subset of functors and specifically applicative functors, even though it's not indicated in Haskell's type system.

Knowing that, given a monad and basing on return and bind, how to:

• derive fmap,
• derive <*> ?

Answer 1

Well, fmap is just (a -> b) -> f a -> f b, i.e. we want to transform the monadic action's result with a pure function. That's easy to write with do notation:

fmap f m = do
  a <- m
  return (f a)

or, written "raw":

fmap f m = m >>= \a -> return (f a)

This is available as Control.Monad.liftM.

pure :: a -> f a is of course return. (<*>) :: f (a -> b) -> f a -> f b is a little trickier. We have an action returning a function, and an action returning its argument, and we want an action returning its result. In do notation again:

mf <*> mx = do
  f <- mf
  x <- mx
  return (f x)

Or, desugared:

mf <*> mx =
  mf >>= \f ->
  mx >>= \x ->
  return (f x)

Tada! This is available as Control.Monad.ap, so we can give a complete instance of Functor and Applicative for any monad M as follows:

instance Functor M where
  fmap = liftM

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

Ideally, we'd be able to specify these implementations directly in Monad, to relieve the burden of defining separate instances for every monad, such as with this proposal. If that happens, there'll be no real obstacle to making Applicative a superclass of Monad, as it'll ensure it doesn't break any existing code. On the other hand, this means that the boilerplate involved in defining Functor and Applicative instances for a given Monad is minimal, so it's easy to be a "good citizen" (and such instances should be defined for any monad).

Answer 2

fmap = liftM and (<*>) = ap. Here are links to the source code for liftM and ap. I presume you know how to desugar do notation.