powerset

[Graham Klyne]

At 11:06 05/06/03 +0200, Jerzy Karczmarczuk wrote:
>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
<GK@NineByNine.org>
PGP: 0FAA 69FF C083 000B A2E9  A131 01B9 1C7A DBCA CB5E