Prolog/Bagof, Setof and Findall

Bagof, Setof and Findall are so called metapredicates, because they take a ":Goal" as an argument. Metapredicates are the equivalent of higher order functions from functional programming languages.

What is a :Goal?

A :Goal is anything that you can feed in to the top level interpreter. For example the simplest metapredicate is call/1.

Call/1 is similar to "eval" in other scripting languages.

We mark goals with the prefix ":" in header comments. It's just a convention we use in documentation, and comments. The Prolog interpreter knows nothing about this convention.

The header comment for call/1 is:

call(:Goal)

Examples:

 ?- call(write('hello')).
 hello
 true.

 ?- call(A=1).
 A = 1.

 ?- X=write('hello'), call(X).
 hello
 X = write(hello).

From the SICSTUS manual:

 call(:Term) [ISO]
 :Term
 If Term is instantiated to a term which would be acceptable as the body of a clause, then the goal call(Term) is  executed 
 exactly as if that term appeared textually in its place, except that any cut (!) occurring in Term only cuts alternatives
 in the execution of Term.

All metapredicates call "call/1" on one way or other.

Finding all the solutions without pushing ";" all the time

Sometimes we want to restrict the standard Prolog backtracking to a block of code, and put all solutions that the backtracking found in to a list that we can use outside of that block. That's when we use "findall/3".

Example: (SWI prolog)

We need modulo division for this example. "mod/2" works the following way:

 ?- A is mod(5,2).
 A = 1.

 ?- A is mod(4,2).
 A = 0.

We also need numlist/3, which simply generates a list of successing integers.

 ?- numlist(1,8,X).
 X = [1, 2, 3, 4, 5, 6, 7, 8].

Now comes the meat: we want to filter the odd numbers from the above list. We use findall/3 for this:

findall(+Template, :Goal, -Bag)

?- findall(X, (numlist(1,8,NL),member(X,NL),0 =:= mod(X,2)) ,L).
L = [2, 4, 6, 8].

As you see, the middle argument is a simple goal. If copy it and feed it to the toplevel interpreter you get the following:

 ?- numlist(1,8,NL),member(X,NL),0 =:= mod(X,2).
 NL = [1, 2, 3, 4, 5, 6, 7, 8],
 X = 2 ;
 NL = [1, 2, 3, 4, 5, 6, 7, 8],
 X = 4 ;
 NL = [1, 2, 3, 4, 5, 6, 7, 8],
 X = 6 ;
 NL = [1, 2, 3, 4, 5, 6, 7, 8],
 X = 8 ;
 false.

The first argument of findall/3 denotes the variable we want to collect in the list in the third argument.

You can read the above example as: find all X where X satisfies :Goal.

Bagof is very similar to this, but you can also use the existential quantifier "^" in the +Template. The variable on which the existential quantifier is applied won't be collected in the resulting list.

Setof is like bagof but the resulting list is ordered and doesn't contain repetitions.

Further examples

Find divisor pairs:

 ?- findall(X-Y, (numlist(1,8,NL),member(X,NL),member(Y,NL),X>Y,Y =\=1, 0 =:= mod(X,Y)), L).
 L = [4-2, 6-2, 6-3, 8-2, 8-4].

The same, but we don't care about Y.

 ?- bagof(X, Y^(numlist(1,8,NL),member(X,NL),member(Y,NL),X>Y,Y =\=1, 0 =:= mod(X,Y)), L).
 NL = [1, 2, 3, 4, 5, 6, 7, 8],
 L = [4, 6, 6, 8, 8].

Filtering out repetition:

 ?- setof(X, Y^(numlist(1,8,NL),member(X,NL),member(Y,NL),X>Y,Y =\=1, 0 =:= mod(X,Y)), L).
 NL = [1, 2, 3, 4, 5, 6, 7, 8],
 L = [4, 6, 8].