CODEWITHSUNDEEP
haskellmonadsfunctorapplicative
Kos
Kos

Reputation: 72281

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

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:

Upvotes: 15

Views: 2127

Answers (2)

dave4420
dave4420

Reputation: 47062

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

Upvotes: 10

ehird
ehird

Reputation: 40797

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).

Upvotes: 26

Related Questions