Q:

Why does it typecheck and how?

I am reading the paper Applcative programming with effects from Conor McBride and Ross Paterson and I can't figure out why their first piece of code typechecks. (I have a strong OCaml background and a weak haskell background).
There is a function ap from Control.Monad with the following type:
ap :: Monad m => m (a -> b) -> m a -> m b

This function can easily be written like this:
ap mf mx = do { f <- mf ; x <- mx ; return (f x) }

Then they write the following:
sequence :: [IO a] → IO [a]
sequence [] = return []
sequence (c : cs) = return (:) `ap` c `ap` sequence cs

My problem is that I can't figure out how to work out the type of (:) `ap` c `ap` sequence cs by hand because the type of (:) is nowhere close to m (a -> b) since it is a -> ([a] -> [a]).
The type of ap (Just (:)) is Maybe a -> (Maybe ([a] -> [a])) just as expected but the typechecker tells me that the type of ap (:) is (a -> [a]) -> a -> [a]. How is this possible?

A:

If you are writing
return (:) `ap` c `ap` sequence cs

Then, with explicit parenthesization, it's
((return (:)) `ap` c) `ap` (sequence cs)

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

For your second question, ap (:) is using the Monad instance for (->) a, where
-- Monad instance for ((->) a)
return x = \_ -> x
x >>= f  = \y -> f (x y) y

so, you have:
ap :: (a -> (b -> c)) -> (a -> b) -> (a -> c)
ap f g = \x -> f x (g x)

If you just looked at the do-block definition of ap and expanded out the definitions.
Chances are that this second question probably isn't going to be too important or critical for now; focus on the answer to the first one for now :)

