# powerset

**Graham Klyne
**
GK@ninebynine.org

*Thu, 05 Jun 2003 17:41:45 +0100*

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