11.2 Collecting Solutions
There may be many solutions to a query. For example, suppose we are working with the database
child(martha,charlotte).
child(charlotte,caroline).
child(caroline,laura).
child(laura,rose).
descend(X,Y) :- child(X,Y).
descend(X,Y) :- child(X,Z),
descend(Z,Y).
Then if we pose the query
?- descend(martha,X).
there are four solutions (namely X=charlotte , X=caroline , X=laura , and X=rose ).
However Prolog generates these solutions one by one. Sometimes we would like to have all the solutions to a query, and we would like them handed to us in a neat, usable, form. Prolog has three built-in predicates that do this: findall, bagof and setof. In essence, all these predicates collect all the solutions to a query and put them in a single list — but there are important differences between them, as we shall see.
The findall/3 predicate
?- findall(Object,Goal,List).
produces a list List of all the objects Object that satisfy the goal Goal . Often Object is simply a variable, in which case the query can be read as: Give me a list containing all the instantiations of Object which satisfy Goal .
Here’s an example. Suppose we’re working with the above database (that is, with the information about child and the definition of descend ). Then if we pose the query
?- findall(X,descend(martha,X),Z).
we are asking for a list Z containing all the values of X that satisfy descend(martha,X) . Prolog will respond
X = _7489 Z = [charlotte,caroline,laura,rose]
But Object doesn’t have to be a variable, it may be a complex term that just contains a variable that also occurs in Goal . For example, we might decide that we want to build a new predicate fromMartha/1 that is true only of descendants of Martha. We could do this with the query:
?- findall(fromMartha(X),descend(martha,X),Z).
That is, we are asking for a list Z containing all the instantiations of fromMartha(X) that satisfy the goal descend(martha,X) . Prolog will respond
X = _7616
Z = [fromMartha(charlotte),fromMartha(caroline),
fromMartha(laura),fromMartha(rose)]
What happens if we ask the following query?
?- findall(X,descend(mary,X),Z).
As there are no solutions for the goal descend(mary,X) in the knowledge base. findall/3 returns an empty list.
Note that the first two arguments of findall/3 typically have (at least) one variable in common. When using findall/3 , we normally want to know what solutions Prolog finds for certain variables in the goal, and we tell Prolog which variables in Goal we are interested in by building them into the first argument of findall/3 .
You might encounter situations, however, where findall/3 does useful work although the first two arguments don’t share any variables. For example, if you are not interested in who exactly is a descendant of Martha, but only in how many descendants Martha has, you can use the following query to find out:
?- findall(Y,descend(martha,X),Z), length(Z,N).
The bagof/3 predicate
The findall/3 predicate is useful, but in certain respects it is rather crude. For example, suppose we pose the query
?- findall(Child,descend(Mother,Child),List).
We get the response
Child = _6947
Mother = _6951
List = [charlotte,caroline,laura,rose,caroline,
laura,rose,laura,rose,rose]
Now, this is correct, but sometimes it would be useful if we had a separate list for each of the different instantiations of Mother .
This is what bagof/3 lets us do. If we pose the query
?- bagof(Child,descend(Mother,Child),List).
we get the response
Child = _7736 Mother = caroline List = [laura,rose] ; Child = _7736 Mother = charlotte List = [caroline,laura,rose] ; Child = _7736 Mother = laura List = [rose] ; Child = _7736 Mother = martha List = [charlotte,caroline,laura,rose] ; no
That is, bagof/3 is more fine-grained than findall/3 . It gives us the opportunity to extract the information we want in a more structured way. Moreover, bagof/3 can also do the same job as findall/3 , with the help of a special piece of syntax, namely ^ :
?- bagof(Child,Mother^descend(Mother,Child),List).
This says: give me a list of all the values of Child such that descend(Mother,Child) , and put the result in a list, but don’t worry about generating a separate list for each value of Mother . So posing this query yields:
Child = _7870
Mother = _7874
List = [charlotte,caroline,laura,rose,caroline,
laura,rose,laura,rose,rose]
Note that this is exactly the response that findall/3 would have given us. Still, if this is the kind of query you want to make (and it often is) it’s simpler to use findall/3 , because then you don’t have to bother explicitly write down the conditions using ^ .
There is one important difference between findall/3 and bagof/3 , namely that bagof/3 fails if the goal that is specified in its second argument is not satisfied (remember, that findall/3 returns the empty list in such cases). So the query bagof(X,descend(mary,X),Z) yields no .
One final remark. Consider again the query
?- bagof(Child,descend(Mother,Child),List).
As we saw above, this has four solutions. But, once again, Prolog generates them one by one. Wouldn’t it be nice if we could collect them all into one list?
And we can. The simplest way is to use findall/3 . The query
?- findall(List,
bagof(Child,descend(Mother,Child),List),
Z).
collects all of bagof/3 ’s responses into one list:
List = _8293
Child = _8297
Mother = _8301
Z = [[laura,rose],[caroline,laura,rose],[rose],
[charlotte,caroline,laura,rose]]
Another way to do it is with bagof/3 :
?- bagof(List,
Child^Mother^bagof(Child,descend(Mother,Child),List),
Z).
List = _2648
Child = _2652
Mother = _2655
Z = [[laura,rose],[caroline,laura,rose],[rose],
[charlotte,caroline,laura,rose]]
This may not be the sort of thing you need to do very often, but it does show the flexibility and power offered by these predicates.
The setof/3 predicate
The setof/3 predicate is basically the same as bagof/3 , but with one useful difference: the lists it contains are ordered and contain no redundancies (that is, no list contains repeated items).
For example, suppose we have the following database
age(harry,13). age(draco,14). age(ron,13). age(hermione,13). age(dumbledore,60). age(hagrid,30).
Now suppose we want a list of everyone whose age is recorded in the database. We can do this with the query:
?- findall(X,age(X,Y),Out).
X = _8443
Y = _8448
Out = [harry,draco,ron,hermione,dumbledore,hagrid]
But maybe we would like the list to be ordered. We can achieve this with the following query:
?- setof(X,Y^age(X,Y),Out).
(Note that, just as with bagof/3 , we have to tell setof/3 not to generate separate lists for each value of Y , and again we do this with the ^ symbol.) This query yields:
X = _8711 Y = _8715 Out = [draco,dumbledore,hagrid,harry,hermione,ron]
Note that the list is alphabetically ordered.
Now suppose we are interested in collecting together all the ages which are recorded in the database. Of course, we could do this with the following query:
?- findall(Y,age(X,Y),Out).
Y = _8847
X = _8851
Out = [13,14,13,13,60,30]
But this output is rather messy. It is unordered and contains repetitions. By using setof/3 we get the same information in a neater form:
?- setof(Y,X^age(X,Y),Out).
Y = _8981
X = _8985
Out = [13,14,30,60]
Between them, these three predicates offer us a great deal of flexibility when it comes to collecting solutions. For many purposes, all we need is findall/3 , but if we need more, bagof/3 and setof/3 are there waiting to help us out. But bear in mind that there is an important difference between findall/3 on the one hand and bagof/3 and setof/3 on the other: findall/3 will return an empty list if the goal has no solutions, whereas bagof/3 and setof/3 would fail in such a situation.
