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 and setof yield collections for individual bindings of the free variables in the goal. setof yields a sorted version of the collection without duplicates. To avoid binding variables, use an existential quantifier expression. For example the goal bagof(Z,X^Y^p(X,Y,Z),Bag) asks for "the Bag of Z's such that there exists an X and there exists a Y such that p(X,Y,Z)". findall acts like bagof with all free variables automatically existentially quantified. In addition findall returns an empty list [] there is no goal satisfaction, whereas bagof fails.?- 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.