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