6.9 All Solutions and Aggregate Predicates

Often there are many solutions to a problem and it is necessary somehow to compare these solutions with one another. The most general way of doing this is to collect all the solutions into a list, which may then be processed in any way desired. So XSB provides ISO-standard predicates such as setof/3, bagof/3, and findall/3 to collect solutions into lists. Sometimes however, one wants simply to perform some aggregate operation over the set of solutions, for example to find the maximum or minimum of the set of solutions. XSB uses tabling and HiLog to provide a general and powerful aggregation facility as discussed in Section 6.9.1.

setof(?Template, +Goal, ?Set)

This predicate may be read as ``Set is the set of all instances of Template such that Goal is provable''. If Goal is not provable, setof/3 fails. The term Goal specifies a goal or goals as in call(Goal). Set is a set of terms represented as a list of those terms, without duplicates, in the standard order for terms (see Section 6.6). If there are uninstantiated variables in Goal which do not also appear in Template, then a call to this evaluable predicate may backtrack, generating alternative values for Set corresponding to different instantiations of the free variables of Goal. Variables occurring in Goal will not be treated as free if they are explicitly bound within Goal by an existential quantifier. An existential quantification can be specified as:

Y ^ G

meaning there exists a Y such that G is true, where Y is some Prolog term (usually, a variable).

Error cases are the same as predicate call/1 (see Section 6.10).

Example: Consider the following predicate:

    p(red,high,1).
    p(green,low,2).
    p(blue,high,3).
    p(black,low,4).
    p(black,high,5).

The goal ?- setof(Color,Height^Val^p(Color,Height,Val),List) returns a single solution:

    Color = _h73
    Height = _h87
    Val = _h101
    L = [black,blue,green,red]

If Height is removed from the sequence of existential variables, so that the goal becomes:
?- setof(Color,Val^p(Color,Height,Val),List)}, the first solution is:

    Color = _h73
    Val = _h87
    Height = high
    L = [black,blue,red];

upon backtracking, a second solution is produced:

    Color = _h73
    Val = _h87
    Height = low
    L = [black,green]

bagof(?Template, +Goal, ?Bag)

This predicate has the same semantics as setof/3 except that the third argument returns an unsorted list that may contain duplicates.

Error Cases are the same as predicate call/1 (see Section 6.10).

Example: For the predicate p/3 in the example for setof/3, the goal
?- bagof(Color,Height^Val^p(Color,Height,Val),L) returns the single solution:

    Color = _h73
    Height = _h87
    Val = _h101
    L = [red,green,blue,black,black];

If Height is removed from the sequence of existential variables, so that the goal becomes: ?- bagof(Color,Val^p(Color,Height,Val),List), the first solution is:

    Color = _h73
    Val = _h87
    Height = high
    L = [red,blue,black];

upon backtracking, a second solution is produced:

    Color = _h73
    Val = _h87
    Height = low
    L = [green,black];

findall(?Template, +Goal, ?List)

Similar to predicate bagof/3, except that variables in Goal that do not occur in Template are treated as existential, and alternative lists are not returned for different bindings of such variables. Note that this means that Goal should not contain existential variables. This makes findall/3 deterministic (non-backtrackable). Unlike setof/3 and bagof/3, if Goal is unsatisfiable, findall/3 succeeds binding List to the empty list.

Error cases are the same as call/1 (see Section 6.10).

Example: For the predicate p/3 in the example for setof/3, the goal
findall(Color,p(Color,Height,Val),L) returns a single solution:

    Color = _h73
    Height = _h107
    Val = _h121
    F = [red,green,blue,black,black]

tfindall(?Template, +Goal, ?List)

Tabling

Note: tfindall/3 may be deprecated in current versions. Please use the predicates described in Section 6.9.1 if possible.

Like findall/3, tfindall/3 treats all variables in Goal that do not occur in Template as existential. However, in tfindall/3, the Goal must be a call to a single tabled predicate.

tfindall/3 allows the user to build programs that use stratified aggregation. If the table to Goal is incomplete, tfindall/3 suspends until the table has been completed, and only then computes List. See Chapter 5 for further discussion of tfindall/3. Like findall/3, if Goal is unsatisfiable, tfindall/3 succeeds binding List to the empty list.

Some of the differences between predicates findall/3 and tfindall/3 can be seen from the following example:

            | ?- [user].
            [Compiling user]
            :- table p/1.
            p(a).
            p(b).
            [user compiled, cpu time used: 0.639 seconds]
            [user loaded]

            yes
            | ?- p(X), findall(Y, p(Y), L).

            X = a
            Y = _922928
            L = [a];

            X = b
            Y = _922820
            L = [a,b];

            no
            | ?- abolish_all_tables.

            yes
            | ?- p(X), tfindall(Y, p(Y), L).

            X = b
            Y = _922820
            L = [b,a];

            X = a
            Y = _922820
            L = [b,a];

            no

Error cases are the same as predicate findall/3 (see above). Also:

table_error

Upon execution Goal is not a subgoal of a tabled predicate.

tbagof(?X, +Goal, ?List) / tsetof(?X, +Goal, ?List)

Tabling

Note: tbagof/3 and tsetof/3 may be deprecated in current versions. Please use the predicates described in Section 6.9.1 if possible.

The standard predicates tbagof/3 and tsetof/3 provide tabled versions of bagof/3 and setof/3 in a similar manner to the way in which tfindall/3 provides a tabled version of findall/3.

X ^ Goal

The system recognises this as meaning there exists an X such that Goal is true, and treats it as equivalent to call(Goal). The use of this explicit existential quantifier outside predicates setof/3 and bagof/3 constructs is superfluous.