for review: aggregate/4

[Thomas Charles CONWAY]

Hi

Can someone please review the following addition to the library?
-- 
ZZ:wq!
^X^C
Thomas Conway               				      conway at cs.mu.oz.au
AD DEUM ET VINUM	  			      Every sword has two edges.

library/std_util.m:
	Add aggregate/4 and unsorted_aggregate/4.
	Although these predicates are currently implemented in terms of
	[unsorted_]solutions and list__foldl, in theory, they can be
	implemented more efficiently (at least unsorted_aggregate can,
	and aggregate probably can).

Index: std_util.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/library/std_util.m,v
retrieving revision 1.89
diff -u -r1.89 std_util.m
--- std_util.m	1997/05/23 10:54:31	1.89
+++ std_util.m	1997/05/26 02:43:51
@@ -114,6 +114,42 @@
 
 %-----------------------------------------------------------------------------%
 
+% aggregate/4 generates all the solutions to a predicate and applies
+% an accumulator predicate to each solution in turn. XXX how can we
+% better describe aggregation?
+% unsorted_aggregate/4 generates the solutions in unsorted order, with
+% possible duplicates; since there are an infinite number of such orders,
+% this must be called from a context in which only a single solution
+% is required.
+%
+% The current implementation is in terms of [unsorted_]solutions and
+% list__foldl, which, for a predicate with N solutions requires O(N)
+% memory, whereas it is possible to implement unsorted_aggregate (and
+% maybe aggregate) to use O(1) memory.
+
+
+:- pred aggregate(pred(T), pred(T, U, U), U, U).
+:- mode aggregate(pred(out) is multi, pred(in, in, out) is det,
+		in, out) is det.
+:- mode aggregate(pred(out) is multi, pred(in, di, uo) is det,
+		di, uo) is det.
+:- mode aggregate(pred(out) is nondet, pred(in, di, uo) is det,
+		di, uo) is det.
+:- mode aggregate(pred(out) is nondet, pred(in, in, out) is det,
+		in, out) is det.
+
+:- pred unsorted_aggregate(pred(T), pred(T, U, U), U, U).
+:- mode unsorted_aggregate(pred(out) is multi, pred(in, in, out) is det,
+		in, out) is cc_multi.
+:- mode unsorted_aggregate(pred(out) is multi, pred(in, di, uo) is det,
+		di, uo) is cc_multi.
+:- mode unsorted_aggregate(pred(out) is nondet, pred(in, di, uo) is det,
+		di, uo) is cc_multi.
+:- mode unsorted_aggregate(pred(out) is nondet, pred(in, in, out) is det,
+		in, out) is cc_multi.
+
+%-----------------------------------------------------------------------------%
+
 	% maybe_pred(Pred, X, Y) takes a closure Pred which transforms an
 	% input semideterministically. If calling the closure with the input
 	% X succeeds, Y is bound to `yes(Z)' where Z is the output of the
@@ -646,6 +682,16 @@
 unsorted_solutions(Pred, List) :-
 	builtin_solutions(Pred, UnsortedList),
 	cc_multi_equal(UnsortedList, List).
+
+%-----------------------------------------------------------------------------%
+
+aggregate(Generator, Accumulator, Acc0, Acc) :-
+	solutions(Generator, Solutions),
+	list__foldl(Accumulator, Solutions, Acc0, Acc).
+
+unsorted_aggregate(Generator, Accumulator, Acc0, Acc) :-
+	unsorted_solutions(Generator, Solutions),
+	list__foldl(Accumulator, Solutions, Acc0, Acc).
 
 %-----------------------------------------------------------------------------%