Sun Apr 8 10:29:43 CEST 2012

Applicative Functors

As is obvious in a sort of Zen way, just look at the API to see what
an abstraction does.  Look at what it really means without going too
much into story..

1. Needs to be a functor (i.e. container) ::  (a -> b) -> f a -> f b

2. It needs to support application        ::   f (a -> b) -> f a -> f b

What I missed before is sequenceA

  sequenceA :: Applicative f => [f a] -> f [a]
  sequenceA cs = c where
    c = foldr push (pure []) cs
    push c cs = (:) <$> c <*> cs

Thinking about this as: convert collection of element PRODUCERS into a
PRODUCER of a collection of elements.  What happens above is
construction using (:) but what if construction is something like:

  Tie the output state of the first to the input of the second.

Something didn't yet click...  But one of the key elements is
sequenceA.  Trying the original paper again[1].

Some observations from [1]:

* These all start from pure functions in the examples (a pure function
  applied to funny arguments).  However, after the first <$>, the
  result is no longer a pure function, but a collection of partially
  applied functions.  The ability to store such a collection is just a
  property of a Functor, i.e. up to here we just used fmap = <$>.
  After that, once we have a *collection* of functors to then further
  apply it to elements that are also in collections requires <*>.

* A reason to define traverse directly is that the usual definition as
  sequence . map will traverse the struture twice (if the compiler can't
  optimize this out that is..)

* The Monoid / phantom Applicative relation seems interesting but
  doesn't quite snap into place for me..  Try later.

* Different between Applicative and Monad: for a Monad the value of
  one computation can influence the second, while for Applicative the
  structure of a computation is fixed.  Moral:

    If you've got Applicative, that's good
    If you've got Monad, that's even better!

    If you need Monad, that's good
    If you need only Applicative, that's even better!

* Applicative are composable.

* Monoidal = symmetric interface for Applicative:
    unit :: f ()
    <,>  :: f a -> f b -> f (a,b)

  This separates the "combination" from the "computation" which can be
  done by fmap, i.e. :: (a,b) -> c.

  Which illustrates an important point: it's the combination of two
  values into one that allows sequentiality to emerge.

[1] http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf