looking for data structure advice

[Conor McBride]

Hi

Sorry to take so long: I've spent a week watching paint dry, so I can
confirm that this is more interesting.

Jon Cast wrote:
> 
> Conor McBride <c.t.mcbride at durham.ac.uk> wrote:
> <snip>
> 
> > I've always been a little bothered by the MonadPlus class: zero and
> > plus are associated (no pun intended) in my mind with monoidal
> > structure.  Is there more to MonadPlus than a clumsy workaround for
> > the lack of quantified constraints?
> 
> Yes.  For every functor m with a MonadPlus instance, m () has /two/
> monoids, (mzero, mplus) and (return (), (>>)).  MonadPlus is thus no
> more a workaround than the category Field; MonadPlus is simply a way to
> specify that a functor has two monoid-like structures, one more exact
> than the other, together with the expectation that the two monoids are
> related in a manner similar to the relationship of the two
> (more-or-less-) groups that make up a field.

That's a fair point. As these fieldy things are two monoids plus
distributive laws, they deserve special recognition. Do they have a name
(semirings, or something?).

Generally speaking, (return (), (>>)) seems to be just one instance of
the fact that if m is a monad and x is a monoid wrt (zero, plus), say,
then (m x) is also a monoid wrt (return zero, liftM2 plus). It's the
ability to push application under m (with appropriate laws) which
makes this possible: monads are just one structure which allows this
to happen.

A non-monadic example: [IO Int] has

  {zero = [], plus = (++),
   one = return (return 0), times = liftM2 (liftM2 (+))}

with distributive laws etc, but ([] . IO) is not monadic.

> > If we could have quantified constraints, e.g.
> >
> >   (Monad m, forall x. Monoid (m x))
> >
> > wouldn't that be better than having Monad-specific monoids?
> 
> No.  Consider the monad Writer (IO ()).  The Writer monad wants a Monoid
> instance, and the most natural such instance is often (return (), (>>)).
> OTOH, this monad is always wrong in the cases where, currently, you
> would use mplus.  So you can't just replace MonadPlus with Monoid; you
> need to be more specific about your choice of monoid than can be
> accounted for by a single class.
> 
> <snip>

This is basically an unfortunate consequence of some design choices in
the class system, rather than a good thing per se. Pragmatically, it's
really annoying, at least to me, that I can't classify both of these
monoid structures as monoids, in order to use monoid-generic operators
(e.g. flattening) on either. I can't help thinking that newtype offers
a better workaround than making the monoidal aspect of MonadPlus not a
Monoid. But I would prefer to have some way to be more specific about
choice of monoid (indeed of instance, generally) in some localized way.

Merry Christmas

Conor