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