[m-dev.] for review: aggregate/4

[Thomas Charles CONWAY]

> Given that there is no efficiency advantage, aggregate/4 doesn't
> really buy you much over just calling solutions/2 and list__foldl/4.
> Is it really worth adding to the library?
> 

Orthogonality.

> How about the following:
> 
> 	% unsorted_aggregate/4 generates all the solutions to a predicate
> 	% and applies an accumulator predicate to each solution in turn:
> 	%
> 	% unsorted_aggregate(Generator, Accumulator, Acc0, Acc) <=>
> 	% 	unsorted_solutions(Generator, Solutions),
> 	% 	list__foldl(Accumulator, Solutions, Acc0, Acc).
> 

Thanks.

Here is a revised diff which I have comitted - the change to the more
efficient implementation can come later as an enhancement.
-- 
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, unsorted_aggregate
	can be implemented more efficiently.

Index: std_util.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/library/std_util.m,v
retrieving revision 1.90
diff -u -r1.90 std_util.m
--- std_util.m	1997/05/26 15:39:21	1.90
+++ std_util.m	1997/05/26 23:01:07
@@ -114,6 +114,49 @@
 
 %-----------------------------------------------------------------------------%
 
+        % aggregate/4 generates all the solutions to a predicate,
+	% sorts them and removes duplicates, then applies an accumulator
+	% predicate to each solution in turn:
+        %
+        % aggregate(Generator, Accumulator, Acc0, Acc) <=>
+        %       solutions(Generator, Solutions),
+        %       list__foldl(Accumulator, Solutions, Acc0, Acc).
+	%
+
+:- 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.
+
+        % unsorted_aggregate/4 generates all the solutions to a predicate
+        % and applies an accumulator predicate to each solution in turn:
+        %
+        % unsorted_aggregate(Generator, Accumulator, Acc0, Acc) <=>
+        %       unsorted_solutions(Generator, Solutions),
+        %       list__foldl(Accumulator, Solutions, Acc0, Acc).
+	%
+	% 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
+	% to use O(1) memory.
+
+:- 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 +689,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).
 
 %-----------------------------------------------------------------------------%