looking for data structure advice

[Conor McBride]

Hi

David Roundy wrote:
> 
> On Mon, Dec 15, 2003 at 08:55:10AM +0000, Graham Klyne wrote:
> > I apologize... my question was unclear.
> >
> > It was not the standard MonadPlus class and functions that I was asking
> > about, but the specific instance for Maybe (i.e. or_maybe).  As it happens,
> > a couple of times in the past couple of weeks, I might have used such a
> > function if it were available in the standard libraries.
> 
> My or_maybe is just defined as
> 
> or_maybe (Just e) _ = Just e
> or_maybe Nothing f = f

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?

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?

Of course, we can always kludge

  class MakesMonoid f where
    makesZero :: f x
    makesPlus :: f x -> f x -> f x

  instance MakesMonoid f => Monoid (f x) where
    mempty = makesZero
    mappend = makesPlus

but that causes serious restrictions on the other monoids we can
declare.

One useful thing about monoids is that they can be lifted pointwise
through product-like structures

  instance (Monoid x,Monoid y) => Monoid (x,y)

  instance Monoid t => Monoid (s -> t)
     -- note this conflicts with the more usual but (I claim)
     -- less useful Monoid (a -> a)

The latter gives us higher-order combinators for the price of
first-order operators. For example, given the `or_maybe'
monoid, we get for free the operation which prioritizes two
partial functions, trying the second only if the first fails.

  mappend :: (s -> Maybe t) -> (s -> Maybe t) -> (s -> Maybe t)

You'd also be amazed how useful the monoid IO () can be...

So I guess this is yet another plea for universally quantified
constraints. Is there a problem with them? I don't see why
(forall x. Monoid (m x)) is harder to check than
(Monoid (m FreshName)). Of course, the next thing after
quantified constraints is constrained constraints, and a big
chunk of lambda-Prolog appearing as one of Haskell's growing
collection of heterogeneous compile-time programming languages.

What a big can of tasty worms...

Cheers

Conor