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"
>powerset(<source>,<possible result>) --- is the pattern. And the
>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?)
PGP: 0FAA 69FF C083 000B A2E9 A131 01B9 1C7A DBCA CB5E