findall, bagof, setof — Collecting All Solutions

Course 1 ended with prolog1-4's backtracking and prolog1-8's cut — both about controlling a search that hands back one solution at a time, via ;. Course 2 opens with the natural next question: what if you want all of them, at once, as an ordinary list you can pass around? That's exactly what findall/3, bagof/3, and setof/3 do — three meta-predicates, genuinely different from each other, that collect a backtracking search's results into one concrete value.

The Problem: Backtracking Gives You Answers One At A Time

Recall the family facts from Course 1:

Each ; press asks Prolog to backtrack and try again. That's fine at the interactive top level, but it's useless inside a program — a predicate that wants "every child of tom, as a list" has no way to press ; for you. Something has to drive the backtracking to exhaustion and gather the results.

findall/3 — The Simplest Collector

findall(Template, Goal, List) runs Goal, collecting Template for every solution found by backtracking, and unifies List with the result — all in one call, no interactive ; needed. This is genuinely close to the mental model Haskell's own list monad gives you (haskell2-3): both collect every result of a nondeterministic computation into one concrete list. The difference is Haskell builds that list through do-notation over [] as a monad instance; Prolog's findall is a dedicated meta-predicate that drives Prolog's own SLD search directly.

findall has one important, very forgiving property: if Goal has no solutions at all, findall still succeeds — with an empty list, not a failure.

bagof/3 — Respecting Free Variables

bagof/3 looks like a drop-in replacement for findall at first glance, but it behaves genuinely differently whenever the goal contains a variable — like Parent below — that isn't in the template:

Instead of one combined list, bagof groups the results by every possible binding of the free variable Parent, backtracking through each group separately. This is a genuine, easy-to-miss surprise coming from findall — the same query, one predicate swapped for another, produces three separate answers instead of one merged list.

To get findall-style behaviour — one combined list, ignoring who the parent was — use the ^ operator to tell bagof to treat Parent as existentially quantified ("for some Parent," not "grouped by Parent"):

setof/3 — Sorted, Deduplicated Results

setof/3 shares bagof's free-variable grouping behaviour exactly, with two extra guarantees: the resulting list is sorted (Prolog's standard order of terms) and has all duplicates removed.

Compare this to what findall would have produced for the same query — [bob, liz, ann, pat, jim], in whatever order the facts were tried and with any duplicates left in. setof is the right choice specifically when the caller needs a canonical, duplicate-free answer rather than a raw trace of the search.

Coding Challenges