[Haskell] A MonadPlusT with fair operations and pruning

[oleg at pobox.com]

On Wed Jan 5 20:17:37 EST 2005, Andrew Bromage wrote on the
Haskell-Cafe mailing list:

> BTW, if someone would like an "interesting" monad to play with, here is
> one that I've been playing with for a while.  It's a nondeterminism
> monad transformer with negation-as-failure and if-then-else with soft
> cut.  The appropriate contexts/continuations for an efficient
> implementation (using the Hughes/Hinze technique) turn out to be quite
> difficult to find.
>
> The operations that we need to implement are:
>
>     - the Monad operations (return and bind),
>     - the MonadTrans operation (lift),
>     - the MonadPlus ones (mzero and mplus), and
>     - one other operation, which plays the role of logical if-then-else.

We have implemented all the above operations, plus "don't care
non-determinism" (aka `once') plus fair conjunctions and disjunctions,
plus bagOfN. We have two implementations of the enhanced MonadPlus
Transformer: one is based on genuine continuations. The other,
direct-style realization, relies on the first-class delimited
continuation transformer library by Sabry, Dybvig, and
Peyton-Jones. The continuation-passing implementation uses two (rather
than three) continuations: success, failure -- but no cut
continuation. Still, control logical operations are supported.  The
continuation-passing implementation was indeed difficult to find,
although the result is deceptively simple.

The code is freely available under the MIT license:
	http://pobox.com/~oleg/ftp/packages/LogicT.tar.gz

Our joint work (with Amr Sabry, Chung-chieh Shan and Daniel
P. Friedman) is described in the paper to be presented at ICFP'05:
	http://pobox.com/~oleg/ftp/papers/LogicT.pdf

Since Andrew Bromage wished for that interesting monad, perhaps he has
in mind a good example of its use. We are particularly interested in a
short example illustrating soft-cut (and, perhaps, `once'). To be
sure, the paper has several examples. Since we have a couple of pages
left, we would like to describe something more extensive. Alas, all
examples we have in mind are either too simple or take too much space
to describe. Comments and suggestions are very appreciated.