Sat Apr 7 11:51:09 CEST 2012

Data.Traversable vs. Data.Foldable

Follow-up from last post.

From [1], a Traversable is a Foldable that is also a Functor.

This can be understood by observing that Foldable will just iterate
and thread a state, while Traversable will iterate, thread state, and
build a new data structure.  If you cancel the output datastructure
you get a fold, while if you cancel the threading you get a map.

What I find strange is that all of these can be seemingly defined in
terms of forM.  Let's try.

The missing insight seems to be that the constraint on traverse is
Applicative, and not Monad.  Why is this?  Below t is the container

    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

The question is: why is a monad not necessary?  Or, why is the "monad
part" of a monad that's more powerful than the "applicative part" not
used?  Last time I was looking into this, the take-home argument was:
monads have value-dependent control flow, while arrows do not.  Not
sure about applicative though.

The important part for the Monad version of traverse is that it
imposes sequential traversal, eventually imposed by the composition of
calls to (>>=).  Can the same be done with applicative?  Maybe my main
problem is that I don't see how applicative imposes sequencing?  Let's
explore that in a separate thread.


The missing link is sequenceA, which bridges lists of computations and
the sequencing operator of an applicative functor.  This makes it sort
of obvious why Traversable just needs sequenceA.

However it seems simpler to define for directly, since this can be
converted to fmap by insert the identity Applicative.

[1] http://www.haskell.org/haskellwiki/Foldable_and_Traversable