How and why is ap defined as liftM2 id in Haskell

Whilst trying to better u开发者_运维问答nderstand Applicative, I looked at the definition of <*>, which tends to be defined as ap, which in turn is defined as:

ap                :: (Monad m) => m (a -> b) -> m a -> m b
ap                =  liftM2 id

Looking at the type signatures for liftM2 and id, namely:

liftM2  :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
id                      :: a -> a

I fail to understand how just by passing in id, the relevant part of the type signature seems to transform from (a1 -> a2 -> r) -> m a1 to m (a -> b). What am I missing here?

---

The type variable a from id can be instantiated at any type, and in this case that type is a -> b.

So we are instantiating id at (a -> b) -> (a -> b). Now the type variable a1 from liftM2 is being instantiated at (a -> b), a2 is being instantiated at a, and r is being instantiated at b.

Putting it all together, liftM2 is instantiated at ((a -> b) -> (a -> b)) -> m (a -> b) -> m a -> m b, and liftM2 id :: m (a -> b) -> m a -> m b.

---

The top answer is definitely correct and works quickly and efficiently from the types alone. Once you are good at Haskell (disclaimer: I am not) then this is a much more efficient way to understand this than to slough through the function definitions.

But since I recently had to struggle through exactly this issue with ap while I was working on The Monad Challenges, I decided to share my experience because it may provide some extra intuition.

First, just as The Monad Challenges asks, I will use the name bind to refer to the primary Monad operator >>=. I think this helps a lot.

If we define our own version of liftM2 we can do this:

liftM2 :: (Monad m) => (a -> b -> c) -> m a -> m b -> m c
liftM2 f ma mb = 
    ma `bind` \a -> 
    mb `bind` \b -> 
    return $ f a b

We want to create ap using this to help us. Let's leave the function f alone for a moment and just think about how this could work as ap assuming we picked the right function for f.

Suppose that we were to pass a function-valued Monad as the first part above, the ma part. It could be something like Just (+3) or [(+3), (*2)] -- some "function" living inside a Monad context.

And we supply an argument-valued Monad as the second part, the mb part, such as Just 5 or [6,7,8] -- some "value" living in a Monad context which can serve as the argument for the function living inside ma.

Then we'd have

liftM2 f (m someFunction) (m someArgument) = 
    (m someFunction) `bind` \a ->
    (m someArgument) `bind` \b ->
    return $ (f a b)

and inside the lambda functions following bind, we know that a will be someFunction and b will be someArgument -- for that is what bind does: it simulates the extraction of a value out of the Monad context modulo any special processing that is unique to that Monad.

So that final line really becomes

return $ f someFunction someArgument

Now let's step back and remember that our goal in creating ap is to call someFunction upon someArgument inside of the Monad context. So whatever our use of return yields, it needs to be the result of the function application someFunction someArgument.

So how can we make the two expressions be equal

f someFunction someArgument ==? someFunction someArgument

Well, if we let x = (someFunction someArgument) then we're looking for a function f such that

f x = x

and so we know that f needs to be id.

Going back to the start, this means we're looking for liftM2 id.

Basically liftM2 id ma mb says I'm going to do m (id a b) so if a is a function that can operate on b, then id will "just leave them alone" and let a do its thing to b, while returning the result inside of the Monad context.

It's like we've forced liftM2 to have bystander bias.

And in order for that to work out, a will have to have a function type that goes from "TypeOfb" to "SomeReturnType", or TypeOfb -> SomeReturnType, because b is a's expected argument. And of course b has to have TypeOfb.

If you'll permit me one abuse of notation, then arbitrarily let's just use the symbol "a" to stand for "TypeOfb" and the symbol "b" to stand for "SomeReturnType":

`b` --> "a" is its type
`a` --> "a -> b" is its type

Then the type signature for ap would be

ap :: Monad m => m (TypeOfB -> SomeReturnType) -> m TypeOfB -> m SomeReturnType
==>
ap :: Monad m => m (a -> b) -> m a -> m b