Non-determinism, backtracking and Monads

[Andrew J Bromage]

G'day all.

On Wed, Jun 11, 2003 at 08:37:48AM +0100, Graham Klyne wrote:

> I was thinking some more about this comment of yours, and my own experience 
> with the ease of using lists to implement prolog-style generators, and 
> think I come to some better understanding.

You might find this amusing:

  http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/hfl/hfl/mtl/Logic.hs?rev=1.2

This monad and monad transformer basically implement ground-moded
logic programming, including if-then-else with soft cut.  (It doesn't
implement Prolog cut, but you really don't want it.)

> So there seems to be a very close relationship between the lazy list and 
> non-deterministic computations, but what about other data structures?  I 
> speculate that other structures, lazily evaluated, may also be used to 
> represent the results of non-deterministic computations, yet allow the 
> results to be accessed in a different order.

Yes.  The different data structures would, in general I think,
correspond to different search rules.  Using a lazy list corresponds
to depth-first search.  Your tree monad actually returns the entire
computation tree, which can then be traversed in depth-first order,
breadth-first order, or whatever order you want.

You have to be careful with monad transformers stacked on top of
non-commutative monads, though.  Most programmers would expect, in
this code:

	(lift m1 `mplus` lift m2) `mplus` lift m3

that both m1 and m2 will be evaluated before m3; at least in
circumstances where it mattered.

Cheers,
Andrew Bromage