Type analysis for McBride's and Paterson's definition of sequence in terms of ap.

McBridePatersonSequenceApTypes.hs

-- See [McBride & Paterson, Applicative Programming with Effects]
-- (www.staff.city.ac.uk/~ross/papers/Applicative.html)

{-
Analysis of types:

Following, from the paper, the definition of `sequence` in terms of `ap` from
`Control.Monad`:

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

Decoding the last equation, it must be parenthesized as follows in prefix form:

  ap (ap (return (:)) c) (sequence cs)

To make it concrete, let

  c  = putStrLn $ show 1 :: IO ()
  cs = map putStrLn (map show [2, 3]) :: [IO ()]

The type of `ap` is

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

so the interior use of `ap` in equation 1 makes sense: the type of `(:)` is
`a->[a]->[a]`. The type of `return (:)' is `Monad m => m (a -> [a] -> [a])`, or
`IO (a -> [a] -> [a])` in context. This meets the spec of the first argument
of `ap`, and we get

  (ap (return (:))) :: IO a -> IO ([a] -> [a])

Now apply it to an IO () like c:

  (ap (ap (return (:)) (putStrLn $ show 1)) :: IO [()] -> [()]

This entire expression, again, meets the spec of `ap`. We get

Incidentally, even with the definition of c as above, GHCi reports

  (ap (return (:)) c) :: ((a -> [a]) -> a) -> ((a -> [a]) -> [a])

and it's too hard to see how this relates to IO [()] -> [()]. We have to say

  (ap (return (:)) (c :: IO ())) :: IO [()] -> [()]

What is the type of cs?

  cs :: [IO ()]

Therefore,

  sequence cs :: IO [()]

just what `(ap (ap (return (:)) (putStrLn $ show 1))` needs. Finally, we get

  ap (ap (return (:)) (c :: IO ())) (sequence cs) :: IO [()]

-}