findall, bagof, and setof

Analogy categoryAnalogies

The All-Solutions Predicates

Prolog's resolution engine finds solutions one at a time through backtracking, but many programs need every solution collected into a single data structure at once. The all-solutions predicates — findall/3, bagof/3, and setof/3 — bridge this gap by running a goal to exhaustion internally and packaging the results as a list, without disturbing bindings in the surrounding clause. Each of the three differs in how it treats free variables, duplicate results, and the case where no solution exists at all, and choosing the right one is a routine but consequential decision in idiomatic Prolog code.

🏏

Cricket analogy: Think of a scorer who, instead of announcing each run as it happens, waits until the innings ends and hands you the full ball-by-ball log at once — that's findall/3 replaying a goal to exhaustion and returning every result as one list, like Sachin Tendulkar's full innings scorecard rather than a live commentary feed.

findall/3: The Workhorse Aggregator

findall(Template, Goal, List) proves Goal repeatedly via backtracking, and for each success instantiates Template and copies it into List; crucially, it never fails — if Goal has zero solutions, List is simply bound to the empty list []. Because findall/3 does not look at variables shared outside Goal in any special way, it is the simplest and most predictable of the three, and it is almost always the right first choice when you just need 'every answer, or an empty list if there are none.'

🏏

Cricket analogy: It's like a net-bowler who runs every delivery of a training session regardless of whether the batter connects, and at the end simply reports zero boundaries if none were hit rather than refusing to give a scorecard — findall/3 always returns a list, empty or not, never failing outright.

prolog

parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).

% findall/3 - always succeeds, may return []
?- findall(Child, parent(tom, Child), Children).
Children = [bob, liz].

?- findall(Child, parent(mia, Child), Children).
Children = [].

% bagof/3 - groups by the free variable Parent unless quantified
?- bagof(Child, parent(Parent, Child), Children).
Parent = tom, Children = [bob, liz] ;
Parent = bob, Children = [ann, pat].

?- bagof(Child, Parent^parent(Parent, Child), Children).
Children = [bob, liz, ann, pat].

% setof/3 - sorted, deduplicated
?- setof(Child, Parent^parent(Parent, Child), Children).
Children = [ann, bob, liz, pat].

bagof/3: Grouping and Existential Quantification

bagof(Template, Goal, List) behaves like findall/3 in collecting results, but with two key differences: it fails (rather than returning []) when Goal has no solutions, and it treats free variables in Goal that don't appear in Template as implicitly grouped — bagof/3 backtracks through distinct bindings of those free variables, producing a separate List for each combination, unless you existentially quantify them away with the ^/2 operator, as in bagof(Child, Parent^parent(Parent, Child), Children), which pools results across all Parent bindings into one list.

🏏

Cricket analogy: It's like asking for 'batting partners of Kohli' without naming the match — bagof/3 backs through each match separately, giving a new partner list per game, unless you tell it with ^ to pool every match into one combined list.

bagof/3 and setof/3 fail outright when Goal has zero solutions — they do not return an empty list the way findall/3 does. If you need 'empty list on no results' semantics along with sorting or grouping, wrap the call: ( setof(X, Goal, L) -> true ; L = [] ).

setof/3: Sorted, Deduplicated Results

setof(Template, Goal, List) adds two more guarantees on top of bagof/3's behavior: the resulting List is sorted into standard order of terms and has all duplicate elements removed, using the same ordering and deduplication rules as the sort/2 predicate. Like bagof/3, setof/3 fails when Goal has no solutions and groups by unbound free variables unless they are existentially quantified with ^, so it is best understood as 'bagof/3 plus automatic sorting and uniqueness' rather than as an unrelated third predicate.

🏏

Cricket analogy: It's like a scorecard app that not only lists every bowler who took a wicket but also alphabetizes them and removes duplicate entries when the same bowler appears in multiple spells — setof/3 does exactly this extra sorting-and-deduping pass on top of bagof/3's grouped results.

Choosing Between Them

In practice, findall/3 is the default choice for simple aggregation since it never fails and ignores grouping subtleties entirely, making it predictable inside larger clauses; reach for bagof/3 when you specifically want per-group results and are prepared to handle failure on empty solutions (often by wrapping the call in (bagof(X, G, L) -> true ; L = [])); and use setof/3 when you additionally need the output sorted and free of duplicates, such as when computing a canonical set of related facts for display or comparison.

🏏

Cricket analogy: It's like choosing between three commentary tools: a raw ball-by-ball log for casual review (findall/3), a per-innings breakdown you use only when you're prepared for 'no data' if an innings didn't happen (bagof/3), and a polished sorted highlights reel with no repeated clips for the post-match show (setof/3).

A quick decision rule: use findall/3 by default; switch to bagof/3 only if you need per-group results and can tolerate (or explicitly guard against) failure on no solutions; switch to setof/3 instead of bagof/3 whenever you also want the output sorted and duplicate-free.

findall/3 never fails — it returns [] when Goal has no solutions.
bagof/3 and setof/3 fail on zero solutions unless wrapped defensively.
bagof/3 and setof/3 group results by unbound free variables in Goal, backtracking through each group unless quantified with ^.
setof/3 additionally sorts results into standard order of terms and removes duplicates.
Use Var^Goal to existentially quantify a free variable so its bindings are pooled rather than treated as separate groups.
findall/3 is the safest default for simple aggregation since it ignores grouping semantics entirely.
All three predicates copy Template into the result list without disturbing bindings outside the call.