Quintus Prolog Manual

G-15: Sets and Bags: Collecting Solutions to a Goal

G-15-0: Introduction

When there are many solutions to a goal, and a list of all those solutions is desired, one means of collecting them is to write a procedure which repeatedly backtracks into that goal to get another solution. In order to collect all the solutions together, it is necessary to use the database (via assertion) to hold the solutions as they are generated, because backtracking to redo the goal would undo any list construction that had been done after satisfying the goal.

The writing of such a backtracking loop can be avoided by the use of one of the built-in predicates setof/3, bagof/3 and findall/3 which are described below. These provide a nice logical abstraction, whereas with a user-written backtracking loop the need for explicit side-effects (assertions) destroys the declarative interpretation of the code. The built-in predicates are also more efficient than those a user could write.

G-15-1: Collecting a Sorted List

setof(Template, Generator, Set) returns the set Set of all instances of Template such that Generator is provable, where that set is non-empty. The term Generator specifies a goal to be called as if by call/1. Set is a set of terms represented as a list of those terms, without duplicates, in the standard order for terms (see Chapter G-9-7).

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 Set will only provide an imperfect representation of what is in reality an infinite set.

If Generator is instantiated, but contains uninstantiated variables which do not also appear in Template, then setof/3 can succeed nondeterminately, generating alternative values for Set corresponding to different instantiations of the free variables of Generator. (It is to allow for such usage that Set is constrained to be non-empty.) For example, if your program contained the clauses

        likes(tom, beer).
        likes(dick, beer).
        likes(harry, beer).
        likes(bill, cider).
        likes(jan, cider).
        likes(tom, cider).

 

        | ?- setof(X, likes(X,Y), S).

 

        X = _872,
        Y = beer,
        S = [dick,harry,tom] ;

        X = _872,
        Y = cider,
        S = [bill,jan,tom] ;

        no

 

        | ?- setof((Y,S), setof(X,likes(X,Y),S), SS).

 

Y = _402,
S = _417,
X = _440,
SS = [(beer,[dick,harry,tom]),(cider,[bill,jan,tom])] ;

no

G-15-1-1: Existential Quantifier

X ^ P is recognized as meaning "there exists an X such that P is true", and is treated as equivalent to simply calling P. The use of the explicit existential quantifier outside setof/3 and bagof/3 is superfluous.

Variables occurring in Generator will not be treated as free if they are explicitly bound within Generator by an existential quantifier. An existential quantification is written:

        Y^Q

        | ?- setof(X, Y^likes(X,Y), S).

 

        X = _400,
        Y = _415,
        S = [bill,dick,harry,jan,tom] ;

        no
 

Furthermore, it is possible to existentially quantify a term, where all the variables in that term are taken to be existentially quantified in the goal. E.g.,

        A=term(X,Y), setof(Z, A^foo(X,Y,Z), L).

 

G-15-2: Collecting a Bag of Solutions

bagof/3 is is exactly the same as setof/3 except that the list (or alternative lists) returned will not be ordered, and may contain duplicates. This relaxation saves time and space in execution.

G-15-2-1: Collecting All Instances

findall/3 is a special case of bagof/3, where all free variables in the generator are taken to be existentially quantified. Thus the use of the operator ^ is avoided. Because findall/3 avoids the relatively expensive variable analysis done by bagof/3, using findall/3 where appropriate rather than bagof/3 can be considerably more efficient.

Previously, findall/3 was available in library(findall).

G-15-3: Library Support

basics sets lists ordsets

G-15-4: Predicate Summary

setof/3 ^/2 bagof/3 findall/3

contact: product support sales information