When there are many solutions to a problem, and when all those solutions are required to be collected together, this can be achieved by repeatedly backtracking and gradually building up a list of the solutions. The following built-in predicates are provided to automate this process.
Note that the Goal argument to the predicates listed
below is called as if by call/1
at runtime. Thus if Goal
is complex and if performance is an issue, define an auxiliary
predicate, which can then be compiled, and let Goal
call it.
setof(
?Template,
:Goal,
?Set)
ISO
Read this as "Set is the set of all instances of Template
such that Goal is satisfied, where that set is non-empty". The
term Goal specifies a goal or goals as in
call(
Goal)
(see Control). Set is a set of
terms represented as a list of those terms, without
duplicates, in the standard order for terms (see Term Compare). If there are no instances of Template such that
Goal is satisfied then the predicate fails.
The variables appearing in the term Template should not appear anywhere else in the clause except within the term Goal. Obviously, the set to be enumerated should be finite, and should be enumerable by Prolog in finite time. It is possible for the provable instances to contain variables, but in this case the list Set will only provide an imperfect representation of what is in reality an infinite set.
If there are uninstantiated variables in Goal, which do not also appear in Template, then a call to this built-in predicate may backtrack, generating alternative values for Set corresponding to different instantiations of the free variables of Goal. (It is to cater for such usage that the set Set is constrained to be non-empty.) Two instantiations are different iff no renaming of variables can make them literally identical. For example, given the clauses:
likes(bill, cider). likes(dick, beer). likes(harry, beer). likes(jan, cider). likes(tom, beer). likes(tom, cider).
the query
| ?- setof(X, likes(X,Y), S).
might produce two alternative solutions via backtracking:
S = [dick,harry,tom], Y = beer ? ; S = [bill,jan,tom], Y = cider ? ;
The query:
| ?- setof((Y,S), setof(X, likes(X,Y), S), SS).
would then produce:
SS = [(beer,[dick,harry,tom]),(cider,[bill,jan,tom])]
Variables occurring in Goal will not be treated as free if they are explicitly bound within Goal by an existential quantifier. An existential quantification is written:
Y^Q
meaning "there exists a Y such that Q is true", where Y is some Prolog variable.
For example:
| ?- setof(X, Y^(likes(X,Y)), S).
would produce the single result:
S = [bill,dick,harry,jan,tom]
in contrast to the earlier example.
Note that in iso
execution mode, only outermost existential
quantification is accepted, i.e. if the Goal argument is
of form V1
^ ... ^
N ^
SubGoal. In
sicstus
execution mode existential quantification is handled also
deeper inside Goal.
bagof(
?Template,
:Goal,
?Bag)
ISO
This is exactly the same as setof/3
except that the list
(or alternative lists) returned will not be ordered, and may
contain duplicates. The effect of this relaxation is to save a call to
sort/2
, which is invoked by setof/3
to return an ordered
list.
?X^
:P
The all solution predicates recognize this as meaning "there
exists an X such that P is true", and treats it as
equivalent to P
(see Control). The use of this
explicit existential quantifier outside the
setof/3
and
bagof/3
constructs is superfluous and discouraged.
findall(
?Template,
:Goal,
?Bag)
ISO
Bag is a list of instances of Template in all proofs
of Goal found by Prolog. The order of the list corresponds
to the order in which the proofs are found. The list may be empty
and all variables are taken as being existentially quantified.
This means that each invocation of findall/3
succeeds
exactly once, and that no variables in Goal get
bound. Avoiding the management of universally quantified
variables can save considerable time and space.
findall(
?Template,
:Goal,
?Bag,
?Remainder)
findall/3
, except Bag is the list of solution
instances appended with Remainder, which is typically
unbound.