Prolog has three built-in predicates designed to collect together objects resulting from successful computations:

bagof(Things, GoalCondition, Bag) setof(Things, GoalCondition, Bag) findall(Things,GoalCondition, Bag)

To illustrate the differences consider a little example:

Try the following goals. (The answer displays have been modified to save space.)listing(p). p(1,3,5). p(2,4,1). p(3,5,2). p(4,3,1). p(5,2,4).

The predicates?- bagof(Z,p(X,Y,Z),Bag). Z = _G182 X = 1 Y = 3 Bag = [5] ; Z = _G182 X = 2 Y = 4 Bag = [1] ; Z = _G182 X = 3 Y = 5 Bag = [2] ; Z = _G182 X = 4 Y = 3 Bag = [1] ; Z = _G182 X = 5 Y = 2 Bag = [4] ; No ?- findall(Z,p(X,Y,Z),Bag). Z = _G182 X = _G180 Y = _G181 Bag = [5, 1, 2, 1, 4] ; No ?- bagof(Z,X^Y^p(X,Y,Z),Bag). Z = _G182 X = _G180 Y = _G181 Bag = [5, 1, 2, 1, 4] ; No ?- setof(Z,X^Y^p(X,Y,Z),Bag). Z = _G182 X = _G180 Y = _G181 Bag = [1, 2, 4, 5] ; No

?- bagof(Z,(p(X,Y,Z),Z>5),Bag). No ?- findall(Z,(p(X,Y,Z),Z>5),Bag). Z = _G182 X = _G180 Y = _G181 Bag = [] Yes

Consider another example. In section 2.5, the 'height' predicate was defined to be

height(Node,H) :- setof(Z,ht(Node,Z),Set), max(Set,0,H).

The 'setof' computation gathers together all of the Zs that result from the 'ht(Node,Z)' computations and lists the distinct (different) Zs in Set. For example,

?- setof(Z,ht(a,Z,Set). Set=[3,4,2,] ?- setof(Z,ht(a,Z),Set), max(Set,0,H). Set=[3,4,2] H=4

where Set=[3,4,2] represents individual results of 'ht' computations of 'a' above its leaf descendants, but the height of 'a' is H=4. The reader will have to go back to section 2.5 for the definitions involving 'ht'. Compare this with:

?- bagof(Z,ht(a,Z),Bag). Bag=[3,3,4,2,3,3,3,3,3,3]

The 'findall' predicate could be simulated as follows:

find-all(X,Goal,Bag) :- post_it(X,Goal), gather([],Bag). post_it(X,Goal) :- call(Goal), /* try Goal */ asserta(data999(X)), /* assert above others */ fail. /* force backtracking */ post_it(_,_). /* gratuitous success */ gather(B,Bag) :- data999(X), /* find next recorded solution */ retract(data999(X)), /* erase posting */ gather([X|B],Bag), /* continue ... */ !. /* cut off rule below */ gather(S,S). /* when done */

The reader should spend some time with these definitions. The 'find-all' definition requires that first all of the answers be posted to memory using 'asserta'. Try various 'asserta(p(Constant))' goals, where 'Constant' has various constant values like 'a', 'b', etc., each followed respectively by a 'listing(p)' goal to see how Prolog asserts. See also the definitions of 'assert', 'asserta', 'assertz' and 'retract' in section 4.9. Secondly, 'find-all' then gathers all of the posted values together into a list.

*Exercise 2.12.1* Modify the 'findall' simulation given in 'find-all' above to create a version
that does not add duplicates. Use 'assert' and 'retract' in similar ways but make sure that 'gather' only
gathers unique Xs that have not been previously gathered.

Prolog Tutorial Contents