Odtnhj

(Note: I'm phrasing the question using Haskell terminology; answers are welcome to use the same terminology and/or the mathematical language of category theory, including proper mathematical definitions and axioms where I speak of functor and monad laws.)

It is well known that every monad is also a functor, with the functor's fmap equivalent to the monad's liftM. This makes sense, and of course holds for all common/reasonable monad instances.

My question is whether this equivalence of fmap and liftM provably follows from the functor and monad laws. If so it will be nice to see how, and if not it will be nice to see a counterexample.

To clarify, the functor and monad laws I know are the following:

• 
  fmap id ≡ id
  


• 
  fmap f . fmap g ≡ fmap (f . g)
  


• 
  return x >>= f ≡ f x
  


• 
  x >>= return ≡ x
  


• 
  (x >>= f) >>= g ≡ x >>= (x -> f x >>= g)
  

I don't see anything in these laws which relates the functor functionality (fmap) to the monad functionality (return and >>=), and so I find it hard to see how the equivalence of fmap and liftM (defined as liftM f x = x >>= (return . f)) can be derived from them. Maybe there is an argument for it which is just not straightforward enough for me to spot? Or maybe I'm missing some laws?

What you have missed is the parametericity law, otherwise known as the free theorem. One of the consequences of parametricity is that all polymorphic functions are natural transformations. Naturality says that any polymorphic function of the form

t :: F a -> G a

where F and G are functors, commutes with fmap:

t . fmap f = fmap f . t

If we can make something involving liftM that has the form of a natural transformation, then we will have an equation relating liftM and fmap. liftM itself doesn't produce a natural transformation:

liftM :: (a -> b) -> m a -> m b
 -- ^______^
 -- these need to be the same

But here's an idea, since (a ->) is a functor:

as :: m a
flip liftM as :: (a -> b) -> m b
 -- F b -> G b

Let's try using parametericity on flip liftM m:

flip liftM m . fmap f = fmap f . flip liftM m

The former fmap is on the (a ->) functor, where fmap = (.), so

flip liftM m . (.) f = fmap f . flip liftM m

Eta expand

(flip liftM m . (.) f) g = (fmap f . flip liftM m) g
flip liftM m (f . g) = fmap f (flip liftM m g)
liftM (f . g) m = fmap f (liftM g m)

This is promising. Take g = id:

liftM (f . id) m = fmap f (liftM id m)
liftM f m = fmap f (liftM id m)

It would suffice to show liftM id = id. That probably follows from its definition:

liftM id m
 = m >>= return . id
 = m >>= return
 = m

Yep! Qed.

For this exercise, I found it easier to work with join rather than >>=. A monad can be equivalently defined through return and join, satisfying

1) join . join = join . fmap join
2) join . return = join . fmap return = id

Indeed, join and >>= are inter-definable:

x >>= f = join (fmap f x)
join x = x >>= id

And the laws you mentioned correspond to those above (I won't prove this).

Then, we have:

liftM f x
= def liftM 
x >>= return . f 
= def >>= 
join (fmap (return . f) x)
= def . and $ 
join . fmap (return . f) $ x
= fmap law 
join . fmap return . fmap f $ x
= join law 2 
id . fmap f $ x
= def id, ., $ 
fmap f x