<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
"http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>
<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.06-7 of 2001-11-14">
<TITLE>
All solutions
</TITLE>
</HEAD>
<BODY TEXT=black BGCOLOR=white>
<A HREF="manual031.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="manual023.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="manual033.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>
<TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#66dbff"><DIV ALIGN=center><TABLE>
<TR><TD><FONT SIZE=4><B><A NAME="htoc101">7.9</A></B></FONT></TD>
<TD WIDTH="100%" ALIGN=center><FONT SIZE=4><B>All solutions</B></FONT></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE><UL>
<LI><A HREF="manual032.html#toc71"> Introduction</A>
<LI><A HREF="manual032.html#toc72"> <TT>findall/3</TT></A>
<LI><A HREF="manual032.html#toc73"> <TT>bagof/3</TT>,
<TT>setof/3</TT></A>
</UL>
<BR>
<A NAME="toc71"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#98e7ff"><DIV ALIGN=center><TABLE>
<TR><TD><B><A NAME="htoc102">7.9.1</A></B></TD>
<TD WIDTH="100%" ALIGN=center><B>Introduction</B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE>
<A NAME="Introduction:(All-solutions)"></A>
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. <BR>
<BR>
The built-in predicates described in this section invoke <TT>call/1</TT>
(section <A HREF="manual022.html#call/1">6.2.3</A>) on the argument <TT>Goal</TT>. When efficiency is crucial
and <TT>Goal</TT> is complex it is better to define an auxiliary predicate
which can then be compiled, and have <TT>Goal</TT> call this predicate.<BR>
<BR>
<A NAME="toc72"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#98e7ff"><DIV ALIGN=center><TABLE>
<TR><TD><B><A NAME="htoc103">7.9.2</A></B></TD>
<TD WIDTH="100%" ALIGN=center><TT><B>findall/3</B></TT></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE>
<BR>
<B>Templates</B>
<DL COMPACT=compact><DT><DD><TT>
findall(?term, +callable_term, ?list)</TT></DL>
<B>Description</B><BR>
<BR>
<TT>findall(Template, Goal, Instances)</TT> succeeds if <TT>Instances</TT>
unifies with the list of values to which a variable <TT>X</TT> not occurring
in <TT>Template</TT> or <TT>Goal</TT> would be instantiated by successive
re-executions of <TT>call(Goal), X = Template</TT> after systematic
replacement of all variables in <TT>X</TT> by new variables. Thus, the order
of the list <TT>Instances</TT> corresponds to the order in which the proofs
are found.<BR>
<BR>
<B>Errors</B><BR>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD BGCOLOR=black COLSPAN=3><TABLE BORDER=0 WIDTH="100%" CELLSPACING=0 CELLPADDING=1><TR><TD></TD></TR></TABLE></TD>
</TR>
<TR><TD VALIGN=top ALIGN=left><TT>Goal</TT> is a variable</TD>
<TD VALIGN=top ALIGN=center NOWRAP> </TD>
<TD VALIGN=top ALIGN=left><TT>instantiation_error</TT></TD>
</TR>
<TR><TD BGCOLOR=black COLSPAN=3><TABLE BORDER=0 WIDTH="100%" CELLSPACING=0 CELLPADDING=1><TR><TD></TD></TR></TABLE></TD>
</TR>
<TR><TD VALIGN=top ALIGN=left><TT>Goal</TT> is neither a variable nor a callable term</TD>
<TD VALIGN=top ALIGN=center NOWRAP> </TD>
<TD VALIGN=top ALIGN=left><TT>type_error(callable, Goal)</TT></TD>
</TR>
<TR><TD BGCOLOR=black COLSPAN=3><TABLE BORDER=0 WIDTH="100%" CELLSPACING=0 CELLPADDING=1><TR><TD></TD></TR></TABLE></TD>
</TR>
<TR><TD VALIGN=top ALIGN=left>The predicate indicator <TT>Pred</TT> of <TT>Goal</TT> does not
correspond to an existing procedure and the value of the <TT>unknown</TT>
Prolog flag is <TT>error</TT> (section <A HREF="manual045.html#set-prolog-flag/2">7.22.1</A>)</TD>
<TD VALIGN=top ALIGN=center NOWRAP> </TD>
<TD VALIGN=top ALIGN=left><TT>existence_error(procedure, Pred)</TT></TD>
</TR>
<TR><TD BGCOLOR=black COLSPAN=3><TABLE BORDER=0 WIDTH="100%" CELLSPACING=0 CELLPADDING=1><TR><TD></TD></TR></TABLE></TD>
</TR>
<TR><TD VALIGN=top ALIGN=left><TT>Instances</TT> is neither a partial list nor a list</TD>
<TD VALIGN=top ALIGN=center NOWRAP> </TD>
<TD VALIGN=top ALIGN=left><TT>type_error(list, Instances)</TT></TD>
</TR>
<TR><TD BGCOLOR=black COLSPAN=3><TABLE BORDER=0 WIDTH="100%" CELLSPACING=0 CELLPADDING=1><TR><TD></TD></TR></TABLE></TD>
</TR></TABLE><BR>
<B>Portability</B><BR>
<BR>
ISO predicate.<BR>
<BR>
<A NAME="toc73"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#98e7ff"><DIV ALIGN=center><TABLE>
<TR><TD><B><A NAME="htoc104">7.9.3</A></B></TD>
<TD WIDTH="100%" ALIGN=center><B><TT>bagof/3</TT>,
<TT>setof/3</TT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE>
<BR>
<B>Templates</B>
<DL COMPACT=compact><DT><DD><TT>
bagof(?term, +callable_term, ?list)<BR>
setof(?term, +callable_term, ?list)</TT></DL>
<B>Description</B><BR>
<BR>
<TT>bagof(Template, Goal, Instances)</TT> assembles as a list the
set of solutions of <TT>Goal</TT> for each different instantiation of the
free variables in <TT>Goal</TT>. 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.<BR>
<BR>
<B>Free variable set</B>: <TT>bagof/3</TT> groups the solutions of
<TT>Goal</TT> according to the free variables in <TT>Goal</TT>. This set
corresponds to all variables occurring in <TT>Goal</TT> but not in
<TT>Template</TT>. It is sometimes useful to exclude some additional
variables of <TT>Goal</TT>. For that, <TT>bagof/3</TT> recognizes a goal of
the form <TT>T^Goal</TT> and exclude all variables occuring in <TT>T</TT>
from the free variable set. <TT>(^)/2</TT> can be viewed as an
<EM>existential quantifier</EM> (the logical reading of <TT>X^Goal</TT>
being ``there exists an <TT>X</TT> such that <TT>Goal</TT> is true''). The
use of this existential qualifier is superfluous outside <TT>bagof/3</TT>
(and <TT>setof/3</TT>) and then is not recognized.<BR>
<BR>
<TT>(^)/2</TT> is a predefined infix operator (section <A HREF="manual037.html#op/3:(Term-input/output)">7.14.10</A>).<BR>
<BR>
<TT>setof(Template, Goal, Instances)</TT> is equivalent to
<TT>bagof(Template,Goal,I), sort(I,Instances)</TT>. Each list is then a
sorted list (duplicate elements are removed).<BR>
<BR>
From the implementation point of view <TT>setof/3</TT> is as fast as
<TT>bagof/3</TT>. Both predicates use an in-place (i.e. destructive) sort
(section <A HREF="manual043.html#sort/2">7.20.12</A>) and require the same amount of memory.<BR>
<BR>
<B>Errors</B><BR>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD BGCOLOR=black COLSPAN=3><TABLE BORDER=0 WIDTH="100%" CELLSPACING=0 CELLPADDING=1><TR><TD></TD></TR></TABLE></TD>
</TR>
<TR><TD VALIGN=top ALIGN=left><TT>Goal</TT> is a variable</TD>
<TD VALIGN=top ALIGN=center NOWRAP> </TD>
<TD VALIGN=top ALIGN=left><TT>instantiation_error</TT></TD>
</TR>
<TR><TD BGCOLOR=black COLSPAN=3><TABLE BORDER=0 WIDTH="100%" CELLSPACING=0 CELLPADDING=1><TR><TD></TD></TR></TABLE></TD>
</TR>
<TR><TD VALIGN=top ALIGN=left><TT>Goal</TT> is neither a variable nor a callable term</TD>
<TD VALIGN=top ALIGN=center NOWRAP> </TD>
<TD VALIGN=top ALIGN=left><TT>type_error(callable, Goal)</TT></TD>
</TR>
<TR><TD BGCOLOR=black COLSPAN=3><TABLE BORDER=0 WIDTH="100%" CELLSPACING=0 CELLPADDING=1><TR><TD></TD></TR></TABLE></TD>
</TR>
<TR><TD VALIGN=top ALIGN=left>The predicate indicator <TT>Pred</TT> of <TT>Goal</TT> does not
correspond to an existing procedure and the value of the <TT>unknown</TT>
Prolog flag is <TT>error</TT> (section <A HREF="manual045.html#set-prolog-flag/2">7.22.1</A>)</TD>
<TD VALIGN=top ALIGN=center NOWRAP> </TD>
<TD VALIGN=top ALIGN=left><TT>existence_error(procedure, Pred)</TT></TD>
</TR>
<TR><TD BGCOLOR=black COLSPAN=3><TABLE BORDER=0 WIDTH="100%" CELLSPACING=0 CELLPADDING=1><TR><TD></TD></TR></TABLE></TD>
</TR>
<TR><TD VALIGN=top ALIGN=left><TT>Instances</TT> is neither a partial list nor a list</TD>
<TD VALIGN=top ALIGN=center NOWRAP> </TD>
<TD VALIGN=top ALIGN=left><TT>type_error(list, Instances)</TT></TD>
</TR>
<TR><TD BGCOLOR=black COLSPAN=3><TABLE BORDER=0 WIDTH="100%" CELLSPACING=0 CELLPADDING=1><TR><TD></TD></TR></TABLE></TD>
</TR></TABLE><BR>
<B>Portability</B><BR>
<BR>
ISO predicates.<BR>
<BR>
<HR SIZE=2>
Copyright (C) 1999-2002 Daniel Diaz
<BR>
<BR>
Verbatim copying and distribution of this entire article is permitted in any
medium, provided this notice is preserved. <BR>
<BR>
<A HREF="index.html#copyright">More about the copyright</A>
<HR>
<A HREF="manual031.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="manual023.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="manual033.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
