BagReduce and BagPO

Actually, XSB provides two basic aggregation operators, bagReduce/4 and bagPO/3, which are used to define all those predicates described in the previous section. We can also use the basic operators to define our own aggregation operators to do specialized things.

The bagReduce/4 predicate takes a bag name, an operator and its identity, and composes the elements of the bag using the operator. For example, we can use bagReduce/4 to define bagSum/2. First we define the sum operator, which must be a 3-ary HiLog operator:

    :- hilog sum.
    sum(X,Y,Z) :- Z is X + Y.

Then we can use this operator in bagReduce/4 to define bagSum/2:

    bagSum(Bag,Res) :- bagReduce(Bag,Res,sum,0).

The bagReduce/4 predicate intuitively works as follows: It finds the first element of the bag, applies the operator to the identity and that element and stores the result in the table. It then finds the second element in the bag, applies the operator to the element in the table and that second element, and replaces the current element in the table by this new result. It continues this way: for each new element the operator is applied to the current value and the new element and the result replaces the current value. The final value in the table is returned as the result.

As another simple example, we can define bagMin/2 by:

    :- hilog minimum.
    minimum(X,Y,Min) :- X =< Y -> Min = X ; Min = Y.

    bagMin(Bag,Res) :- bagReduce(Bag,Res,minimum,1.0e+38).

(assuming that 1.0e+38 is the maximum representable number.)

A slightly more complicated example is the definition of bagAvg/2, which requires a more complex operator that must both sum and count the elements of the bag. It can be defined as follows:

    :- hilog sumcount.
    sumcount([S|C],X,[S1|C1]) :- S1 is S+X, C1 is C+1.

    bagAvg(Bag,Avg) :- 
        bagReduce(Bag,[Sum|Count],sumcount,[0|0]),
        Avg is Sum/Count.

The bagPO/3 operator is also a metapredicate in that it takes a predicate as a parameter. It takes a HiLog binary predicate that defines a partial order. Given a bag, it returns nondeterministically all the maximal elements in the bag under the given partial order.

Consider the following example in which we try to find nice ways to explore a park while going from one point to another in it. Say the park has various interesting things to see and paths between them. We'll represent the paths in the park as a directed acyclic graph, with the points of interest as the nodes. (Both the acyclicity and the directedness of the graph might be somewhat unrealistic, but they can both be relaxed.) The goal now is, given a source and a destination node, find all ``maximal'' paths from the source to the destination. The idea is that we want to take a more-or-less direct route to our target, but we'd like to see as many points of interest as is reasonable along the way.

The following program will compute the set of such maximal paths.

    :- import bagPO/3 from aggregs.
    :- import member/2,append/3 from basics.

% stroll(X,Y,Path) if Path is a way to go from X to Y seeing many things.
    stroll(X,Y,Path) :- bagPO(walk(X,Y),BPath,subset), reverse(BPath,Path).

% subset(L1,L2) if L1 is a subset of L2.
    :- hilog subset.
    subset([],_L).
    subset([X|L1],L2) :- member(X,L2), subset(L1,L2).

% L is in walk(X,Y) if L is a (reversed) path from X to Y.
% (must be tabled because of left-recursion.)
    :- table walk(_,_)(_).
    walk(X,Y)([Y,X]) :- edge(X,Y).
    walk(X,Y)([Y|P]) :- walk(X,Z)(P), edge(Z,Y).

Here walk(X,Y) is a parameterized predicate name which represents the set of paths that go from node X to node Y. Each path is represented as a list of nodes (in reverse order of traversal.) The bagPO aggregation takes just the maximal paths, since we want the alternatives that allow us to see as many points of interest as possible. Here is the execution of the program on the data shown.

    edge(a,b).
    edge(b,c).
    edge(b,d).
    edge(c,d).
    edge(d,e).
    edge(a,f).
    edge(f,g).
    edge(g,e).

| ?- [aggreg].
[aggreg loaded]

yes
| ?- stroll(a,e,P).

P = [a,b,c,d,e];

P = [a,f,g,e];

no
| ?-

Some aggregate operations can be implemented using either bagReduce/4 or bagPO/3. bagMax/2 is a good example. Both of the following definitions are correct:

    :- hilog maximum.
    maximum(X,Y,Z) :- X >= Y -> Z = X ; Z = Y.
    bagMax(Bag,Max) :- bagReduce(Bag,Max,maximum,-1.0e38).

    :- hilog lt.
    lt(X,Y) :- X < Y.
    bagMax(Bag,Max) :- bagPO(Bag,Max,lt).

In such cases it is more efficient to use BagReduce/4 because it can take advantage of the fact that at any point in time, there will be at most one value in the table.