Subject: Re: [SWIPL] using bagof

From: "Richard A. O'Keefe" <[email-masked]>
Date: Mon, 19 Feb 2001 12:46:19 +1300 (NZDT)

Rastei Amelia Viorela  <[email-masked]> wrote:

    Prolog has two built-in predicates designed to collect together objects
    resulting from successful computations: 
	
Three.
	
	bagof(Things, Condition, Bag)
	setof(Things, Condition, Bag)
	
The first argument is not a collection of things, it is a template
exhibiting the shape of ONE thing.  To call the second argument a
"condition" may be misleading, it is a GENERATOR of results.  And
the last argument of setof/3 is not a Bag, it is a Set.   So

    findall(Template, Goal, List)
    bagof(Template, Generator, Bag)
    setof(Template, Generator, Set)

Existential quantifiers in the Goal of a findall/3 have no special effect,
but the use of existential quantifiers in the Generator of a bagof/3 or
setof/3 call is often essential.

Examples such as

    height(Node, H) :- setof(Z, ht(Node, Z), Set), max(Set, 0, H).
	'setof' computes a Set of distinct results. 
	
completely miss the point that has Cecilia Wong confused.

Suppose we have

    p(a, 1, y).
    p(a, 2, x).
    p(b, 1, v).
    p(b, 2, w).

?- findall(X, p(a,N,X), Xs).
 => var(X), var(N), Xs = [y,x].

?- setof(X, N^p(a,N,X), Xs).		N is existentially quantified
 => var(X), var(N), Xs = [x,y].		Xs is sorted with duplicates removed

?- setof(X, p(a,N,X), Xs).		N is ***SOLVED FOR***
 => var(X), N = 1, Xs = [x]
  | var(X), N = 2, Xs = [y]

It is this last use that could not possibly work in a reasonable way
if setof/3 were ever allowed to return an empty list.

?- setof(N-Xs, setof(X, p(a,N,X), Xs), Answers).
 => var(N), var(Xs), var(X),
    Answers = [1-[x],2-[y]].

and this nested use of setof/3 depends on variables not in the template
and not existentially quantified being SOLVED FOR by the inner call to
setof/3, hence relies on setof/3 never returning an empty list.

The Quintus library includes

    setofall(Template, Generator, Set)
    bagofall(Template, Generator, Bag)

which check that the Generator has no free variables, and in that case
*are* willing to return an empty Set or Bag.  That's the equivalent of
not/1 checking for a ground goal.  Just as \+ /1, which does not wait
for its argument to be ground nor check that it is ground, is known to
be logically unsound, so setof/3 and bagof/3 would be logically unsound
if they returned an empty list without checking that their Generator has
no free variables.