Programming challenge: wildcard exclusion in cartesian products

Dinko Tenev dinko.tenev at gmail.com
Tue Mar 21 10:51:17 CET 2006


wkehowski at cox.net wrote:
> After the basic fact of generating the exclusion - a considerable
> achievement - the program should be interactive. What if the target set
> has thousands or millions of elements? There should be a  loop-like way
> ('do' in Haskell, for example) to peel off the elements one-by-one and
> then terminate.

Um..."interactivity" is a bit tricky in Prolog ;)

As Geoffrey pointed out in his posting, the solutions are generated
effectively one at a time.  Following is a typical example of using the
generator:

    generate_member( X, ... ), do_something_with( X ), fail.

The underlying semantics is, roughly, 1) bind X, 2) do_something_with(
X ), 3) fail, meaning reject this binding of X and backtrack.  In this
particular case, backtracking is tantamount to going back to 1).

You can regard ( generate_member( X, ... ) ... fail ) as the equivalent
of a loop construct, and do_something_with( X ) as the loop body.  At
any given time that the goal is being evaluated, there is only one
binding for X in effect.

On a side note, Haskell's "do" notation isn't really about loops.  If
you're referring to Tomasz's code, it's rather mapM_ that can sort of
be thought of as looping through the list of values returned by
generateNotMatching :)

Cheers,

Dinko




More information about the Python-list mailing list