powerset

[Jerzy Karczmarczuk]

Graham Klyne wrote:
> At 15:08 04/06/03 +0100, Liyang HU wrote:
> 
>> A key point is to try and think of how you can relate one case of the
>> problem to a simpler instance of the same problem, rather than 
>> tackling it
>> head on.
> 
> 
> I think that's a good idea to hang on to.  Sometimes easier to say than 
> to do, it seems.


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).

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.

Such things are sometimes easier to do than to describe...




Jerzy Karczmarczuk