Andrew Coppin wrote:
Wuh? What's Traversable?
> In general, one way to make the composition of two
> monads m and n into a monad is to write a function n (m a) -> m (n a);
> this is the sequence method of a Traversable instance for n.
Oh, *that's* Traversable?
Mind you, looking at Data.Traversable, it demands instances for
something called "Foldable" first (plus Functor, which I already happen
to have).
(Looking up Foldable immediately meantions something called "Monoid"...
I'm rapidly getting lost here.)
It sounds like you've figured things out now, but just to chime in. The
problem is that there are a number of different type classes that all
tackle different perspectives on the same thing, or rather, slightly
different things.
These things ---Foldable, Traversable, Monoid, Functor, Applicative,
Monad, MonadPlus, MonadLogic--- they each capture certain basic concepts
that apply to the majority of "normal" data structures. In a very real
sense, these patterns are the core of what category theory is about. And
yet, if you were to try to draw out a venn diagram for them, you'd end
up with something that looks more like a lotus[1] than an OO hierarchy.
For each of these type classes, having one or two of them implies having
many of the rest, regardless of which two you start with. And yet, they
are all different and there are examples of reasonable data structures
which lack one or more of these properties. This circularity makes it
hard to figure out where to even begin. In category theory terminology,
a monad is a monoid on the category of endo-functors. Similarly, list is
the free monoid on any set. Even if you don't grok the terminology,
seeing some of this circularity in definitions should give perspective
on why there's such a tangled mess of type classes.
Ultimately, each of these classes is trying to answer the question: what
is a function? Often it's not helpful to discuss arbitrary functions,
but thankfully most of the functions we're interested in are in fact
very well behaved, and these classes capture the families of structure
we find in those functions. Data structures too can be thought of as
functions, and their mathematical structures are often just as well behaved.
To start in the middle, every Monad is also an Applicative functor and
every Applicative is also a Functor. The situation is actually more
complicated than that since a monad can give rise to more than one
functor (and I believe applicative functors do the same), but it's a
good approximation to start with. If the backwards compatibility issues
could be resolved, it'd be nice to clean up these three classes by
making a type-class hierarchy out of them. (Doing a good job of it would
be helped by some tweaks in how type classes are declared, IMO.)
MonadPlus is for Monads which are also monoids. If you're familiar with
semirings, you can think of (>>=) as conjunction and `mplus` as
representing choice. As others've said, an important distinction is that
MonadPlus universally quantifies over the 'elements' in the monad,
whereas Monoid doesn't. This means that the monoidal behavior of
MonadPlus is a property of the structure of the monad itself, rather
than a property of the elements it contains or an interaction between
the two. In a similar vein is MonadLogic which is a fancier name for
lists or nondeterminism.
Foldable and Traversable are more datastructure-oriented, though they
can be for abstract types (i.e. functions). Foldable is for structures
than can be consumed in an orderly fashion, and Traversable is for
structures that can be reconstructed. A minimal definition for
Traversable gives you a function |t (f a) -> f (t a)| that lets you
distribute the structure over any functor. With that function alone, you
can define instances for Foldable and Functor; conversely, with Foldable
and Functor you can usually write such a function. In some cases, this
is too stringent a requirement since you may be able to distribute
particular <t,f> pairs but not all of them. The category-extras library
has mechanisms for dealing with this, similar to how Monoid lets one
express special cases where the fully general MonadPlus cannot be defined.
[1] http://z.about.com/d/healing/1/0/X/v/art_lotus_12009915A.jpg
--
Live well,
~wren
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
