Implementation of `sequence` with `ap`

Question

Applicative Programming with Effects, the paper from McBride and Paterson, mentions the sequence function:

sequence :: [IO a ] -> IO [a ]
sequence []       = return []
sequence (c : cs) = return (:) `ap` c `ap` sequence cs

where ap's type is:

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

I'm trying to understand the types of the last line's right-side.

How do the types unify (I think that's the correct wording) for return (:) 'ap' c 'ap' sequence cs?

It's not clear to me how return (:) matches ap's first argument m (a -> b).

ghci> :t return (:)
return (:) :: Monad m => m (a -> [a] -> [a])

Answer 1

The answer is... currying! The first argument to ap has type m (a -> b), so the function expects a value of type a and will product a value of type b. One possible thing that b could be is another function (i.e. b could be unified with [a] -> [a]). So, we line things up and get

ap         :: Monad m => m (a -> b         ) -> m a -> m b
                                 ==========
return (:) :: Monad m => m (a -> [a] -> [a])

The ap function performs application of a function in some context (in this case a monad) to a value in that context, it just so happens that it is often used to perform a sequence of partial applications.