[Haskell-cafe] Stacking monads

[wren ng thornton]

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