JLH.Vivek%SU-SIERRA@sri-unix.UUCP (10/15/83)
From: Vivek Sarkar <JLH.Vivek@SU-SIERRA>
One way of defining is_all in "pure" Prolog is as follows:
/* is_all( A, Q ) asserts that A is the list of all distinct
terms that satisfy Q; assume that Q is unary */
is_all( A, Q ) :- is_all_but( A, Q, [] ) .
/* is_all_but( A, Q, X ) asserts that A is the list of all
terms that satisfy Q, but are NOT in list X. If X is empty
then A is the list of all terms that satisfy Q, which is
what we want. */
is_all_but( A, Q, X ) :- A = [ H | T ],
Q( H ),
not_in( H, X),
is_all_but( T, Q, [ H | X ] ) .
is_all_but( [], Q, X).
/* If the previous clause fails then A must be empty. */
not_in( H, [ Hx | Tx ] ) :- not( H = Hx ), not_in( H, Tx ) .
not_in( H, [] ).
So, the list of all terms that satisfy a predicate can be obtained
by carrying around a partial list of generated terms, and using it
to ensure that the next term is distinct from all previous terms.
Obviously, this solution is slower than one which uses assert's,
or a similar global memory mechanism (E.g. writing onto a file).
It is slower because, in generating the ith instantiation (say)
produced by Q, we start at the beginning and call Q i times,
rather than continuing from the (i-1)th instantiation. I'd be
interested to know of a ``pure'' Prolog solution, which avoids this
extra computation.
-- Vivek Sarkar