Re: looking for data structure advice

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