Wed Feb 24 21:16:14 CET 2010

Applicative programming with effects.

I'm reading [1] again.  It's about ``pure functions applied to funny

Some aha's of a concrete-minded Schemer:

 * map in Scheme is map, zipWith, zipWith2, ... in Haskell.
   These need to be different functions as they have different
   type signatures.

 * The S and K combinators are `ap' and `return' from the environment
   (reader) monad.  The paper says that S & K are ``designed for this
   purpose''.  That's the first time I hear this.  But surely, looking
   at S indeed it applies proto-function and proto-argument to an
   environment, and applies the resulting function to the resulting

Now the concrete-minded mind needs to take a distance from looking at
a functor as a data structure over which one maps a function
piecewize, and instead see it as a computation.  Best to start with
monads, as each monad is a AF.

What I don't quite get is this idea of "pure function & effects" where
the <*> operator combines effects and the `pure' operator lifts a pure
function into the effectful domain.

Let's start with

  sequence :: (Monad m) => [m a] -> m [a]

just as in the paper.  This function takes a list of computations and
produces a list of results, threading the monadic effect.

  sequence [] = return []
  sequence (c:cs) = do
     x <- c
     xs <- sequence cs
     return (x:xs)

Which can be written differently as:

  sequence [] = return []
  sequence (c:cs) = pure (:) <*> c <*> sequence cs

The paper then generalizes this to `traverse'.  The key point being
that the recursive call is _inside_ the effectful world.

Now I can't bridge this explanation with the type signature of an
applicative functor:

  pure  :: x -> a x
  (<*>) :: a (x->y) -> a x -> a y

Probably for the same reason that I couldn't see this for Monads in
the beginning.  My intuitive confusion there was that I was looking at
`a' as a data constructor and a type constructor at the same time.

To state the (now) obvious: The two lines above are part of a class
definition `Applicative a', where `a' is a type variable of kind * ->
*, I.e.  a parameteric type with one parameter.  The `Applicative' is
(like) a predicate on type variables.

[1] http://www.cs.nott.ac.uk/~ctm/IdiomLite.pdf