[Haskell-cafe] Re: The mother of all functors/monads/categories

[David Menendez]

On Sun, Jun 27, 2010 at 1:26 PM, Sebastian Fischer
<sebf at informatik.uni-kiel.de> wrote:
> Hi Max,
>
> very interesting observations!
>
>> By the way, you can use this stuff to solve the restricted monad
>> problem (e.g. make Set an instance of Monad). This is not that useful
>> until we find out what the mother of all MonadPlus is, though, because
>> we really need a MonadPlus Set instance.
>
> I'm not sure whether this is TMOA MonadPlus, but here is a set monad with
> MonadPlus instance (code below).

Any continuation monad can be made an instance of MonadPlus if the
final value is a monoid. But whether that serves your purposes or not
depends on what specific properties you want mplus to have.

It's also worth asking why you might prefer the set monad to the list
monad. It has some nice properties (it's commutative and idempotent),
but you can get that by using the list monad internally and only
allowing observation of the values after converting to Set.

There's also the efficiency angle. In the list monad, this expression:

    return x `mplus` return x >>= f

will calculate (f x) twice. In principle, the set monad can avoid
this, but in the continuation-based implementation, this evaluates to
\k -> Set.union (f x >>- k) (f x >>- k), which is just as inefficient
as the list monad.

-- 
Dave Menendez <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>