Sat Apr 7 13:21:05 CEST 2012

Applicative and sequential operations

Monads impose sequential operation through bind (>>=, >>) or the
Kleisli composition (>=>).  This translates easily to "do" notation
(let* for the schemers) which makes the sequentiall nature obvious.

However, Applicative functors also supposedly abstract side effects,
though I've never really understood what these "less powerful" side
effects really are.

In essence, what's the real difference between Applicative and Monad?

This SO article[1] says:

  Compared to monads, applicative functors cannot run its arguments
  selectively. The side effects of all the arguments will take place.

Obviously the difference is to be found in the API, so this would be
the difference between <*> and >>=.

The bridge between lists and sequencing seems to be this function:

  \a as -> (:) <$> a <*> as :: Applicative f => f a -> f [a] -> f [a]

which can be used in a foldr to turn a list of computations [f a] into
a computation that produces a list f [a].

I think I just rediscovered sequenceA for lists:

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

That fills a gaping hole in my understanding.  Life will be different
from now on ;)

Combining sequenceA and map then gives traverse/for.

It's interesting how sequenceA is part of Traversable, i.e. that there
is no less generic version in Prelude that only works on lists.  Maybe
that's a good thing actually - more general from the start.

Letting this sink in for a bit it makes perfect sense: The sequential
nature of Applicative functors should really be compatible with
sequentially traversing a complex data structure.

[1] http://stackoverflow.com/questions/2104446/how-do-you-use-control-applicative-to-write-cleaner-haskell
[2] http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Foldable.html
[3] http://www.haskell.org/ghc/docs/6.12.1/html/libraries/base/Control-Applicative.html
[4] http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-
[5] http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-