Thu, 05 Jun 2003 11:06:24 +0200
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"
powerset(<source>,<possible result>) --- is the pattern. And the
powerset(,). Since nothing else can be done. Otherwise you pick the item
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...