looking for data structure advice

[Jon Cast]

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.

> 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>

Jon Cast