Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 40 ยท Data Structures and Parsing

findall, bagof, setof and aggregate_all

Collect all solutions of a goal in Prolog. Compare findall/3, bagof/3 and setof/3, understand free variables and the ^ operator, and count, sum and find maxima with aggregate_all/3.

Backtracking gives you solutions one at a time. Often you want them all at once, in a list: every child of a parent, every employee in a department, the number of orders over a limit. Prolog has three standard predicates for this, findall/3, bagof/3 and setof/3, plus the convenient aggregate_all/3 in SWI-Prolog. They differ in how they treat variables that are not part of the answer, in whether they fail on no solutions, and in sorting. Knowing which one to reach for is a mark of a fluent Prolog programmer.

All examples use this small database of people and ages:

PROLOG
age(peter, 7).
age(ann, 11).
age(pat, 8).
age(tom, 5).
age(mike, 11).

findall/3

findall(Template, Goal, List) runs Goal to exhaustion and collects a copy of Template for each solution.

PROLOG
?- findall(N, age(N, _), Names).
Names = [peter, ann, pat, tom, mike].

?- findall(A-N, age(N, A), Pairs).
Pairs = [7-peter, 11-ann, 8-pat, 5-tom, 11-mike].

?- findall(N, age(N, 100), Names).
Names = [].

Properties worth memorizing:

  • It always succeeds (with [] if there are no solutions) and never backtracks.
  • Results come in the order the solutions were found, with duplicates.
  • Every variable in Goal that does not appear in Template is simply ignored. There is no grouping.
  • The list holds copies, so it contains fresh variables if the template had unbound ones.

The next demo runs findall in the stand-in engine. Prolog is not available on this site, so this is a small Python interpreter that supports facts, rules and findall.

Python findall over a small database (Python stand-in engine)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

bagof/3 and free variables

bagof(Template, Goal, List) is like findall/3, with two differences. It fails when there are no solutions. And it groups by free variables: variables that occur in Goal but not in Template. For each distinct binding of the free variables, it produces one solution with the matching items.

PROLOG
?- bagof(N, age(N, A), Names).
A = 5,  Names = [tom] ;
A = 7,  Names = [peter] ;
A = 8,  Names = [pat] ;
A = 11, Names = [ann, mike].

Here A is free, so bagof returns one group per age, ordered by the standard order of the free-variable bindings. This is a "group by" in one predicate. If you do not want grouping, mark the variable as existentially quantified with ^:

PROLOG
?- bagof(N, A^age(N, A), Names).
Names = [peter, ann, pat, tom, mike].

Read A^age(N, A) as "there exists an A such that age(N, A)". It tells bagof that A is not free. With ^ in place, bagof behaves like findall but fails on no solutions.

setof/3

setof(Template, Goal, Set) is bagof/3 with the result sorted (standard order) and without duplicates.

PROLOG
?- setof(A, N^age(N, A), Ages).
Ages = [5, 7, 8, 11].

?- setof(A-N, age(N, A), Sorted).
Sorted = [5-tom, 7-peter, 8-pat, 11-ann, 11-mike].

Pairs Key-Name sort by key, and then by name for ties. That makes setof the shortest way to produce a sorted report. To find the youngest person, take the first element of the sorted pairs:

PROLOG
?- setof(A-N, age(N, A), [_-Youngest|_]).
Youngest = tom.

Because setof and bagof fail when nothing matches, the usual defensive form wraps them with a default:

PROLOG
names_older_than(Limit, Names) :-
    (   setof(N, A^(age(N, A), A > Limit), Names)
    ->  true
    ;   Names = []
    ).

Note A^(...) around a conjunction: the caret applies to the whole conjunction of goals in parentheses.

Which one do I use?

findall All solutions, in order, [] when none.
bagof Groups by free variables. Fails when none.
setof Like bagof, sorted, no duplicates.

Use ^ to say a variable is not a grouping key.

1 / 2

aggregate_all/3

SWI-Prolog's library(aggregate) offers shortcuts for the most common reductions:

PROLOG
?- aggregate_all(count, age(_, _), Count).
Count = 5.

?- aggregate_all(sum(A), age(_, A), Total).
Total = 42.

?- aggregate_all(max(A), age(_, A), Oldest).
Oldest = 11.

?- aggregate_all(bag(N), age(N, 11), Names).
Names = [ann, mike].

count, sum(Expr), max(Expr), min(Expr), bag(T) and set(T) are the common forms. Like findall/3, aggregate_all/3 has no grouping: it treats all solutions as one collection. count and sum succeed with 0 on an empty set, while max and min fail. A related form max(Expr, Witness) returns the winning pair, for example aggregate_all(max(A, N), age(N, A), max(MaxAge, Who)).

A grouping model in Python

The stand-in below mimics bagof (grouping by the free variable) and setof (sorted, no duplicates) on the same data, so you can see what the free-variable grouping does.

Python bagof groups, setof sorts (Python model)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Choosing the right predicate

  • Need a plain list of everything, empty allowed: findall/3.
  • Need results per group (per department, per age): bagof/3 without ^, or setof/3 when you also want sorted output.
  • Need a sorted, deduplicated list: setof/3 with ^ for the variables you do not group by.
  • Need a count, sum, maximum: aggregate_all/3.
  • Need to check something for all solutions rather than collect them: forall/2 from the previous lesson.

Common mistakes

  • Forgetting ^ in setof/bagof and getting several partial answers when you wanted one list.
  • Using findall/3 when you want to group by a variable: it loses the grouping.
  • Forgetting that bagof and setof fail on empty results and that findall does not.
  • Leaving variables unbound in the template of findall, which then appear as fresh variables in the list.
  • Calling findall with a goal that never terminates (for example an unbounded generator). Always bound it with between/3 or a limit.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does findall(X, member(X, []), L) return?

    findall always succeeds, with an empty list when there are no solutions. bagof and setof would fail.
  2. 2. In bagof(N, age(N, A), L), why does Prolog return several answers?

    Free variables (in the goal but not the template) make bagof backtrack over each distinct binding.
  3. 3. What does A^age(N, A) tell bagof?

    The caret marks a variable as 'there exists', removing it from the grouping key.
  4. 4. Which gives a sorted list without duplicates?

    setof sorts and removes duplicates; bagof keeps order and duplicates; findall has no grouping.

Summary

  • findall/3 collects all solutions, never fails, ignores free variables and keeps duplicates and order.
  • bagof/3 groups by free variables and fails when empty; X^Goal removes a variable from the grouping.
  • setof/3 is bagof/3 plus sorting and duplicate removal.
  • aggregate_all/3 provides count, sum, max, min, bag and set shortcuts.

Next: The Dynamic Database