Non-determinism, backtracking and Monads

[Jerzy Karczmarczuk]

Graham Klyne wrote on the subject of powerset through backtracking:

> 
> The common thread here is a non-deterministic calculation in which there 
> are several possible solutions for some problem.  The goal is to find 
> (a) if there are any solutions, and (b) one, more or all of the solutions.
> 
> Prolog does this, absent ! (cut), by backtracking through the possible 
> solutions.
> 
> My first epiphany is that the Haskell idea of using a lazily evaluated 
> list for result of a non-deterministic computation is pretty much the 
> same thing (which is pretty much what you said?  Is this what you mean 
> by "the non-deterministic monad"?).  The mechanisms for accessing a list 
> mean that the solutions must be accessed in the order they are 
> generated, just like Prolog backtracking.

Yes. I didn't invent any wheel, just pointed out that in these cases the
remark "easier to say than to do" is too sad. The translation from Prolog
may be really automatic, although the simple-minded result is polluted with
(++) and concat.


> 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.  And these, too, may be 
> (should be?) monads.  

Of course, one can produce lazy trees and other plexes. Most of them are
naturally Functors, but in the general case I am not sure whether there is
a natural way to implement >>= for any shape...

===

On the other hand there is a Monadic Niche elsewhere which is *very different*
from the manipulation of lazy lists, and yet may be used for similar purposes.
I mean: the continuation business.

It is possible, instead of implementing the *data backtracking* through lazy
lists, to make lazy "backtrackable" continuations, permitting to redirect the
flow of control to produce something else. The two ways are - perhaps not
entirely equivalent, but essentially two orchestrations of the same 
                          theme.
I lost my references, perhaps somebody?...

Jerzy Karczmarczuk