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]) ```

Accepted Answer

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.

Implementation of `sequence` with `ap`

Solution

Problem