Previous | Table of Contents | Next |
6.3.7.1. findall
findall takes three parameters: The first is a term pattern, the second is a goal, and the third is a term that collects the solutions. For instance, the goal findall(Y, (grandparent(X, Y), rich(Y)), RichGrands) collects into RichGrands all the Ys such that (grandparent(X, Y), rich(Y)) is truethat is, all the rich grandparents of X. Here is a similar but more complex goal:
findall( wealth(Y,W), (grandparent(X, Y), (rich(Y) -> W=rich ; W=not_rich)), GrandsWealths )
This goal collects into GrandsWealths a list of terms of the form wealth(Y,W), where Y is a grandparent of X and W is rich if that grandparent is rich and not_rich otherwise. The predicate works in the way you might expect: It solves the goal in its second argument and then keeps retrying it and finding new solutions until the goal fails. If the goal goes into an infinite loop, or if it returns an infinite number of solutions, the findall call loops indefinitely as well. This predicate gives us a straightforward way of programming the union and intersection of lists:
union(L1, L2, L) :- findall(E, (member(L1, E); member(L2, E)), L). intersection(L1, L2, L) :- findall(E, (member(L1, E), member(L2, E)), L).
The union of two lists is all the elements that appear in either of the lists, and the intersection is all the elements that appear in both of the lists. This is not the most efficient way of computing the union because the effect of the body is simply to append the two lists, keeping duplicates of any elements that appear in both lists, but it illustrates the potential of findall to help provide an elegant and readable expression of a problem.
Note that in findall, the variables in the first argument work in a rather different way from most variables in Prolog code. Usually, the appearance of a local variable X in the body of a predicate corresponds to the phrase there exists an X; here, it corresponds to the phrase for all Xs. The uninstantiated variables that appear in the second argument but not the first are there exists variables, as is the third argument. The effect of this is achieved by special low-level code that inspects the internal representation of terms and goals; findall cannot be programmed by conventional Prolog clauses.
6.3.7.2. bagof and setof
One effect of the behavior of findall is that it always succeeds exactly once. It calls the goal in its second argument and compiles a list (which may be empty) of the successful patterns. Because of its treatment of uninstantiated variables, no variables get instantiated during a call to findall except the third argument.
This may not be exactly what we want. We may in fact want uninstantiated variables in the second argument to be instantiated to values that make the query succeed. This is what bagof and setof do. For instance, consider again the father predicate:
father(henry_viii, henry_vii). father(margaret_tudor, henry_vii). father(mary_queen_of_scots, james_v_of_scotland). father(elizabeth_i, henry_viii). father(james_v_of_scotland, james_iv_of_scotland).
If we ask the query findall(Child, father(Child, Father), Children), we get Children instantiated to a list of all the people who appear in the first argument in the father relation. However, if we ask bagof(Child, father(Child, Father), Children), we get four solutions:
Children = [henry_viii,margaret_tudor], Father = henry_vii ? ; Children = [elizabeth_i], Father = henry_viii ? ; Children = [james_v_of_scotland], Father = james_iv_of_scotland ? ; Children = [mary_queen_of_scots], Father = james_v_of_scotland ?
As you can see, bagof treats the Father variable (and all uninstantiated variables in the second argument not appearing in the first) as if it is a regular Prolog variable, to be instantiated to whatever satisfies the query. Only the variables appearing in the first argument are treated as for all variables.
Because of this behavior, bagof fails if no solutions exist to the query in the second argument, and it can succeed multiple times upon backtracking. If this is not what you wantthat is, if you just want a simple list of solutions, which may be emptyfindall is the correct predicate to use.
setof is very similar to bagof but differs in its final processing of the list returned. bagof returns a list of solutions that may contain duplicates and is unordered (hence its name, because bag is another word for set possibly containing duplicates). In contrast, setof sorts its list and eliminates all duplicates. In a sense, setof is the most logical of the three all-solutions predicates because the list it returns is ordered not by the order in which the solutions were found, but by lexicographic order.
Previous | Table of Contents | Next |