All solutions predicates

Author(s): First version by Richard A. O'Keefe and David H.D. Warren. Changes by Mats Carlsson, Daniel Cabeza, and Manuel Hermenegildo.

Version: 1.5#118 (2000/4/19, 18:13:43 CEST)

Version of last change: 1.5#115 (2000/4/12, 12:17:22 CEST)

This module implements the standard solution aggregation predicates.

When there are many solutions to a problem, and when all those solutions are required to be collected together, this can be achieved by repeatedly backtracking and gradually building up a list of the solutions. The following built-in predicates are provided to automate this process.

• Usage and interface (aggregates)
• Documentation on exports (aggregates)

Usage and interface (aggregates)

Documentation on exports (aggregates)

PREDICATE: setof/3:

Meta-predicate with arguments: setof(?,goal,?).

Usage: setof(@(Template),+Generator,?(Set)) * ISO *

• Description: Finds the Set of instances of the Template satisfying Generator. The set is in ascending order (see section Comparing terms for a definition of this order) without duplicates, and is non-empty. If there are no solutions, setof fails. setof may succeed in more than one way, binding free variables in Generator to different values. This can be avoided by using existential quantifiers on the free variables in front of Generator, using ^/2. For example, given the clauses:

  father(bill, tom).
  father(bill, ann).
  father(bill, john).
  father(harry, july).
  father(harry, daniel).
  

  The following query produces two alternative solutions via backtracking:

  ?- setof(X,father(F,X),Sons).
  
  F = bill,
  Sons = [ann,john,tom] ? ;
  
  F = harry,
  Sons = [daniel,july] ? ;
  
  no
  ?- 
  

• The following properties should hold upon exit: Template is any term. (basic_props:term/1) Generator is a term which represents a goal, i.e., an atom or a structure. (basic_props:callable/1) Set is a list. (basic_props:list/1)

PREDICATE: bagof/3:

Meta-predicate with arguments: bagof(?,goal,?).

Usage: bagof(@(Template),+Generator,?(Bag)) * ISO *

• Description: Finds all the instances of the Template produced by the Generator, and returns them in the Bag in the order in which they were found. If the Generator contains free variables which are not bound in the Template, it assumes that this is like any other Prolog question and that you want bindings for those variables. This can be avoided by using existential quantifiers on the free variables in front of the Generator, using ^/2.

PREDICATE: findall/3:

Meta-predicate with arguments: findall(?,goal,?).

Usage: findall(?(Template),+Generator,?(List)) * ISO *

• Description: A special case of bagof, where all free variables in the Generator are taken to be existentially quantified. Faster than the other aggregation predicates.

PREDICATE: findall/4:

Meta-predicate with arguments: findall(?,goal,?,?).

Usage: findall(?(Template),+Generator,?(List),?(Tail)) * ISO *

• Description: As findall/3, but returning in Tail the tail of List.

PREDICATE: findnsols/4:

findnsols(N,Template,Generator,List)

As findall/3, but generating at most N solutions of Generator. Thus, the length of List will not be greater than N. If N=<0, returns directly an empty list. This predicate is especially useful if Generator may have an infinite number of solutions.

Meta-predicate with arguments: findnsols(?,?,goal,?).

PREDICATE: findnsols/5:

findnsols(N,Template,Generator,List,Tail)

As findnsols/4, but returning in Tail the tail of List.

Meta-predicate with arguments: findnsols(?,?,goal,?,?).

PREDICATE: ^/2:

Usage: X ^ P

• Description: Existential quantification: X is existentially quantified in P. E.g., in A^p(A,B), A is existentially quantified. Used only within aggregation predicates. In all other contexts, simply, execute the procedure call P.

Go to the first, previous, next, last section, table of contents.