[comp.lang.prolog] I need your help on 'bagof'

mazda@shako.sk.tsukuba.junet (Noriyuki Mazda) (09/04/89)

Hello: 

   I/F Prlog, which I have to use for teaching undergrad. students, does
not have 'setof' and 'bagof'.  With a help of my friend, I now have
a set of clauses to handle 'setof', but still have trouble with 'bagof'.

   Can anyone tell me how to program 'bagof'?

   Thanks in advance.


   MAZDA, Noriyuki
          Inst. of Socio-Economic Planning, Univ. of Tsukuba
          Nihon (also called Nippon or Japan)
   mazda@shako.sk.tsukuba.ac.jp

ok@cs.mu.oz.au (Richard O'Keefe) (09/05/89)

In article <345@shako.sk.tsukuba.junet>, mazda@shako.sk.tsukuba.junet (Noriyuki Mazda) writes:
>    I/F Prolog, which I have to use for teaching undergrad. students, does
> not have 'setof' and 'bagof'.  With a help of my friend, I now have
> a set of clauses to handle 'setof', but still have trouble with 'bagof'.

If you can't hack bagof/3, it's pretty well certain that your setof/3 is
broken, because
	setof(Template, Generator, Set) :-
		bagof(Template, Generator, Bag),
		sort(Bag, Set).

Roughly,
	bagof(Template, Generator, Bag) :-
		free_variables(Generator, Template, FreeVars),
		(   FreeVars = [] ->
		    findall(Template, Generator, Bag),
		    Bag \== []
		;   FreeVars = [_|_] ->
		    findall(FreeVars-Template, Generator, Pairs),
		    /* see below */
		    keysort(Pairs, PairsGroupedByFreeVars),
		    clump(PairsGroupedByFreeVars, FreeVars, Bag)
		).

	free_variables(Generator, Template, FreeVars) :-
		/* scan Generator looking for free variables */
		/* i.e. variables not in Template and not in */
		/* an existential quantifier */

	clump([Key1-Val1,....,Keyn-Valn], Key, [Vali,...,Valj]) :-
		[Key-Vali,...,Key-Valj] is a sublist of the first
		argument all with the same Key, and is as long as
		possible.

In 1984 a public-domain version of DEC-10 Prolog's bagof/3 and setof/3
was posted to the net.  It goes to some trouble in the equivalent of
the second findall/3 call to try to put the original variables back.
I haven't got a copy of that version any more.

Note:	bagof/3 preserves the order of solutions.
	Any bagof/3 which reorders solutions with the same bindings
	for the free variables is broken.
Note:	bagof/3 enumerates the bags in sorted order, but the order in which
	the free variables are placed in the list FreeVars is _not_ defined,
	so portable programs cannot rely on the order in which the bags are
	enumerated.
Note:	setof/3 sorts the elements of the Set into standard order;
	any setof/3 which uses a different order is broken.

Note:	None of which means that you can't have all-solutions predicates
	which use different orders, just that you shouldn't call them
	bagof/3 or setof/3.

The public-domain bagof/3 made it clear that existential quantifiers are
supposed to be noticed anywhere inside the generator, e.g.
	bagof(X, Y^p(X,Y), Xs)
and	bagof(X, (true, Y^p(X,Y)), Xs)
and	bagof(X, (*,Y,*)^p(X,Y), Xs)
are supposed to have the same effect.  Unfortunately, many Prolog
implementors have not taken advantage of the public-domain code, and have
broken this, so that portable programs can't rely on it.