I permit myself to observe that your powerset problem (and the restricted length problem, i.e. the combinations) is usually solved in Prolog, through backtracking, using reasoning/style which adopts this "individualistic" philosophy.
powerset(<source>,<possible result>) --- is the pattern. And the solution is
powerset([],[]). Since nothing else can be done. Otherwise you pick the item or not.
powerset([X|Rest],L) :- powerset(Rest,L). powerset([X|Rest],[X|L) :- powerset(Rest,L).
If my (rusty) Prolog serves, this will still fail to generate the shorter sequences before the longer ones, as I think that all powerset members not containing X must be generated before any that do contain X.
(Or is that a different thread of discussion I'm introducing here?)
The xxx ++ map (x :) xxx solution in Haskell is a particular formulation (and optimization) of the straightforward transformation from a version using the non-deterministic Monad. This one is really almost a carbon copy of the Prolog solution, with appropriate "lifting" of operations from individuals to lazy lists.
It is the case that I'm finding it very easy to code solutions that work very much like Prolog backtracking using what I think is a form of "non-deterministic Monad" (e.g. a list, lazily evaluated, used to return the set of all results?)
#g
------------------- Graham Klyne <[EMAIL PROTECTED]> PGP: 0FAA 69FF C083 000B A2E9 A131 01B9 1C7A DBCA CB5E
_______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
