Relationship between fmap and bind

Question

After looking up the Control.Monad documentation, I'm confused about this passage:

The above laws imply:

fmap f xs = xs >>= return . f

How do they imply that?

Surgical

Answer 1

Control.Applicative says

As a consequence of these laws, the Functor instance for f will satisfy

fmap f x = pure f <*> x

The relationship between Applicative and Monad says

pure = return

(<*>) = ap

ap says

return f `ap` x1 `ap` ... `ap` xn

is equivalent to

liftMn f x1 x2 ... xn

Therefore

fmap f x = pure f <*> x
         = return f `ap` x
         = liftM f x
         = do { v <- x; return (f v) }
         = x >>= return . f

Fortin

Well, this just pushes the question down to the Applicative level. That is: why is fmap f x = pure f <*> x a consequence of the Applicative laws? After all, they don't even mention fmap! And then to answer that, you need @duplode's observation about parametricity... – Labors

Answer 2

Functor instances are unique, in the sense that if F is a Functor and you have a function foobar :: (a -> b) -> F a -> F b such that foobar id = id (that is, it follows the first functor law) then foobar = fmap. Now, consider this function:

liftM :: Monad f => (a -> b) -> f a -> f b
liftM f xs = xs >>= return . f

What is liftM id xs, then?

liftM id xs
xs >>= return . id
-- id does nothing, so...
xs >>= return
-- By the second monad law...
xs

liftM id xs = xs; that is, liftM id = id. Therefore, liftM = fmap; or, in other words...

fmap f xs  =  xs >>= return . f

epheriment's answer, which routes through the Applicative laws, is also a valid way of reaching this conclusion.

Canonry

I think the substitutions are more straightforward in my answer but yours expresses more of the intuition for why it should be. – Fortin

Answer 3

Let me contribute a more self-contained description of why this equality holds:

---

So, why is x >>= (return . f) = fmap f x?

This follows from the three monad laws and parametricity (for free). This means:

Consider the function return :: forall a. F a. Because this function must work over all types a it cannot not change or create new elements of type a but only duplicate or forget values of type a. Therefore, it does not matter whether we apply any function f :: a -> c to change all as into cs before or after applying return.

On the left we apply f on the argument of return, on the right we apply f on the result:

return (f v) = fmap f (return v)                       (free theorem for return)

Similarly, consider the function >>= :: forall a b. F a -> (a -> F b) -> F b. Because this function must work over all types a it cannot not change or create new elements of type a but only duplicate or forget values of type a. Therefore, it does not matter whether we apply any function f :: a -> c to change all as into cs before or after applying >>=.

On the left we apply f on the argument of >>=, on the right we apply f on the result:

x >>= (fmap f . g)  =  fmap f (x >>= g)                (free theorem for bind)

If we now simply instantiate g=return, we get:

x >>= (fmap f . return)  =  fmap f (x >>= return)

To this equation, we can apply on the left hand side the free theorem of return (fmap f . return = return . f), and on the right hand side the left-unit monad law (x >>= return = x):

x >>= (return . f)  =  fmap f x

Done.

Ichthyosis

I think answers aimed at Haskell programmers are probably more helpful if they use standard Haskell notation. I like proper quantifier symbols as much as the next logician, but not everyone learning Haskell is going to have the background to recognise pure: ∀ a, F a as equivalent to pure :: forall a. a -> F a (and in fact aren't you missing an a →?), and some will probably be confused wondering how the list-specific map and : got involved. – Brindle

I was looking for a self-contained answer on this for functional programming in general :) , but i guess the question was aimed at haskell directly. I edited my answer -- do you think its better now? – Ichthyosis