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.