All solutions

6.9

All solutions

6.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 5.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.

6.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 6.22.1) existence_error(procedure, Pred)

Instances is neither a partial list nor a list type_error(list, Instances)

Portability

ISO predicate.

6.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 6.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 6.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 6.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,2000 Daniel Diaz

Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved.

More about the copyright