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