CODEWITHSUNDEEP
haskellmonadsfunctor
user6102088
user6102088

Reputation:

Relationship between fmap and bind

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?

Upvotes: 5

Views: 1423

Answers (3)

drcicero
drcicero

Reputation: 190

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.

Upvotes: 1

duplode
duplode

Reputation: 34398

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.

Upvotes: 8

ephemient
ephemient

Reputation: 204926

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

Upvotes: 8

Related Questions