Subject: Re: [SWIPL] using bagof

From: Rastei Amelia Viorela <[email-masked]>
Date: Fri, 16 Feb 2001 09:00:38 +0200 (EET)

Dear Cecilia,

   I hope this will help:

  Prolog has two built-in predicates designed to collect together objects
resulting from successful computations: 

bagof(Things, Condition, Bag)
setof(Things, Condition, Bag)

For example, 

height(Node,H) :- setof(Z,ht(Node,Z),Set),
                  max(Set,0,H).

The 'setof' computation gathers together all of the Zs that result from
the 'ht(Node,Z)' computations and lists the distinct (different) Zs in
Set. For example, 

if the tree is

            a
	/   |   \ 
       /    |    \
      b     c      d
    / \    / |\    |
   e   f  g  h  i  j
   |  /\  | /\  /|\
   k l  m n o p q r s
          |
          t

?- setof(Z,ht(a,Z,Set)).
Set=[3,4,2]

?- setof(Z,ht(a,Z),Set), max(Set,0,H).
Set=[3,4,2] H=4

where Set=[3,4,2] represents individual results of 'ht' computations of
'a' above its leaf descendants, but the height of 'a' is
H=4. Predicate 'ht' gives the hight of a node in a tree. Compare this
with: 

?- bagof(Z,ht(a,Z),Bag).
Bag=[3,3,4,2,3,3,3,3,3,3]

Generally, 'bagof' computes a Bag of all possibilities with repeats, and
'setof' computes a Set of distinct results. 

The standard 'bagof' predicate could be simulated as follows: 

bag-of(X,Goal,Bag) :-   post_it(X,Goal),
                        gather([],Bag).

post_it(X,Goal) :- call(Goal),         /* try Goal */
                   asserta(data999(X)) /* assert above others */
                   fail.               /* force backtracking   */
post_it(_,_).                          /* gratuitous success    */

gather(B,Bag) :-  data999(X),          /* find next recorded solution  */
                  retract(data999(X)), /* erase posting       */
                  gather([X|B],Bag),   /* continue  ...        */
                  !.                   /* cut off rule below */
gather(S,S).                           /* when done          */

The reader should spend some time with these definitions. The 'bag-of'
definition requires that first all of the answers be posted to memory
using 'asserta'. Try various 'asserta(p(Constant))' goals, where
'Constant' has various constant values like 'a', 'b', etc., each followed
respectively by a 'listing(p)' goal to see how Prolog asserts.

-- 

 Amelia Rastei,
 Dept. Computer Science,
 Babes Bolyai University,
 Cluj Napoca, Romania.