How does <*> derived from pure and (>>=)?

Question

class Applicative f => Monad f where
       return :: a -> f a
       (>>=) :: f a -> (a -> f b) -> f b

(<*>) can be derived from pure and (>>=):

fs <*> as =
    fs >>= (\f -> as >>= (\a -> pure (f a)))

For the line

fs >>= (\f -> as >>= (\a -> pure (f a)))

I am confused by the usage of >>=. I think it takes a functor f a and a function, then return another functor f b. But in this expression, I feel lost.

Answer 1

Lets start with the type we're implementing:

(<*>) :: Monad f => f (a -> b) -> f a -> f b

(The normal type of <*> of course has an Applicative constraint, but here we're trying to use Monad to implement Applicative)

So in fs <*> as = _, fs is an "f of functions" (f (a -> b)), and as is an "f of as".

We'll start by binding fs:

(<*>) :: Monad f => f ( a -> b) -> f a -> f b
fs <*> as
  = fs >>= _

If you actually compile that, GHC will tell us what type the hole (_) has:

foo.hs:4:12: warning: [-Wtyped-holes]
    • Found hole: _ :: (a -> b) -> f b
      Where: ‘a’, ‘f’, ‘b’ are rigid type variables bound by
               the type signature for:
                 (Main.<*>) :: forall (f :: * -> *) a b.
                               Monad f =>
                               f (a -> b) -> f a -> f b
               at foo.hs:2:1-45

That makes sense. Monad's >>= takes an f a on the left and a function a -> f b on the right, so by binding an f (a -> b) on the left the function on the right gets to receive an (a -> b) function "extracted" from fs. And provided we can write a function that can use that to return an f b, then the whole bind expression will return the f b we need to meet the type signature for <*>.

So it'll look like:

(<*>) :: Monad f => f ( a -> b) -> f a -> f b
fs <*> as
  = fs >>= (\f -> _)

What can we do there? We've got f :: a -> b, and we've still got as :: f a, and we need to make an f b. If you're used to Functor that's obvious; just fmap f as. Monad implies Functor, so this does in fact work:

(<*>) :: Monad f => f ( a -> b) -> f a -> f b
fs <*> as
  = fs >>= (\f -> fmap f as)

It's also, I think, a much easier way to understand the way Applicative can be implemented generically using the facilities from Monad.

So why is your example written using another >>= and pure instead of just fmap? It's kind of harkening back to the days when Monad did not have Applicative and Functor as superclasses. Monad always "morally" implied both of these (since you can implement Applicative and Functor using only the features of Monad), but Haskell didn't always require there to be these instances, which leads to books, tutorials, blog posts, etc explaining how to implement these using only Monad. The example line given is simply inlining the definition of fmap in terms of >>= and pure (return)¹.

I'll continue to unpack as if we didn't have fmap, so that it leads to the version you're confused by.

If we're not going to use fmap to combine f :: a -> b and as :: f a, then we'll need to bind as so that we have an expression of type a to apply f to:

(<*>) :: Monad f => f ( a -> b) -> f a -> f b
fs <*> as
  = fs >>= (\f -> as >>= (\a -> _))

Inside that hole we need to make an f b, and we have f :: a -> b and a :: a. f a gives us a b, so we'll need to call pure to turn that into an f b:

(<*>) :: Monad f => f ( a -> b) -> f a -> f b
fs <*> as
  = fs >>= (\f -> as >>= (\a -> pure (f a)))

So that's what this line is doing.

1. Binding fs :: f (a -> b) to get access to an f :: a -> b
2. Inside the function that has access to f it's binding as to get access to a :: a
3. Inside the function that has access to a (which is still inside the function that has access to f as well), call f a to make a b, and call pure on the result to make it an f b

---

¹ You can implement fmap using >>= and pure as fmap f xs = xs >>= (\x -> pure (f x)), which is also fmap f xs = xs >>= pure . f. Hopefully you can see that the inner bind of your example is simply inlining the first version.