Node:All Solutions, Next:Messages and Queries, Previous:Blackboard Primitives, Up:Built Intro

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(`

(see Control).`Goal`)`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

. In`V1`^ ... ^`N`^`SubGoal``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

(see Control). The use of this explicit existential quantifier outside the`P``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`)- Same as
`findall/3`

, except`Bag`is the list of solution instances appended with`Remainder`, which is typically unbound.