7.9 | All solutions

- Introduction
- `findall/3`
- `bagof/3`, `setof/3`

7.9.1 | Introduction

It is sometimes useful to collect all solutions for a goal. This can be done by repeatedly backtracking and gradually building the list of solutions. The following built-in predicates are provided to automate this process.
The built-in predicates described in this section invoke `call/1` (section 6.2.3) on the argument `Goal`. When efficiency is crucial and `Goal` is complex it is better to define an auxiliary predicate which can then be compiled, and have `Goal` call this predicate.

7.9.2 | `findall/3`

Templates

  `findall(?term, +callable_term, ?list)`

Description
`findall(Template, Goal, Instances)` succeeds if `Instances` unifies with the list of values to which a variable `X` not occurring in `Template` or `Goal` would be instantiated by successive re-executions of `call(Goal), X = Template` after systematic replacement of all variables in `X` by new variables. Thus, the order of the list `Instances` corresponds to the order in which the proofs are found.
Errors

`Goal` is a variable |  | `instantiation_error`
`Goal` is neither a variable nor a callable term |  | `type_error(callable, Goal)`
The predicate indicator `Pred` of `Goal` does not correspond to an existing procedure and the value of the `unknown` Prolog flag is `error` (section 7.22.1) |  | `existence_error(procedure, Pred)`
`Instances` is neither a partial list nor a list |  | `type_error(list, Instances)`

Portability
ISO predicate.

7.9.3 | `bagof/3`, `setof/3`

Templates

  `bagof(?term, +callable_term, ?list)
  setof(?term, +callable_term, ?list)`

Description
`bagof(Template, Goal, Instances)` assembles as a list the set of solutions of `Goal` for each different instantiation of the free variables in `Goal`. The elements of each list are in order of solution, but the order in which each list is found is undefined. This predicate is re-executable on backtracking.
Free variable set: `bagof/3` groups the solutions of `Goal` according to the free variables in `Goal`. This set corresponds to all variables occurring in `Goal` but not in `Template`. It is sometimes useful to exclude some additional variables of `Goal`. For that, `bagof/3` recognizes a goal of the form `T^Goal` and exclude all variables occuring in `T` from the free variable set. `(^)/2` can be viewed as an existential quantifier (the logical reading of `X^Goal` being ``there exists an `X` such that `Goal` is true''). The use of this existential qualifier is superfluous outside `bagof/3` (and `setof/3`) and then is not recognized.
`(^)/2` is a predefined infix operator (section 7.14.10).
`setof(Template, Goal, Instances)` is equivalent to `bagof(Template,Goal,I), sort(I,Instances)`. Each list is then a sorted list (duplicate elements are removed).
From the implementation point of view `setof/3` is as fast as `bagof/3`. Both predicates use an in-place (i.e. destructive) sort (section 7.20.12) and require the same amount of memory.
Errors

`Goal` is a variable |  | `instantiation_error`
`Goal` is neither a variable nor a callable term |  | `type_error(callable, Goal)`
The predicate indicator `Pred` of `Goal` does not correspond to an existing procedure and the value of the `unknown` Prolog flag is `error` (section 7.22.1) |  | `existence_error(procedure, Pred)`
`Instances` is neither a partial list nor a list |  | `type_error(list, Instances)`

Portability
ISO predicates.

Copyright (C) 1999-2002 Daniel Diaz
Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved.
More about the copyright