[m-dev.] for review: additions to the library

[David Overton]

Hi,

Would someone please review these additions to the library.

David

----------------------

Estimated hours taken: 2

Add a few predicates and functions to the library.

library/map.m:
	Add predicate map__foldl2 and functions map__search,
	map__insert and map__update.

library/tree234.m:
	Add predicate tree234__foldl2.

library/std_util.m:
	Add predicate aggregate2 and functions solutions,
	solutions_set and aggregate.

News:
	Mention the changes.

Index: NEWS
===================================================================
RCS file: /home/mercury1/repository/mercury/NEWS,v
retrieving revision 1.175
diff -u -r1.175 NEWS
--- NEWS	2000/09/21 09:43:40	1.175
+++ NEWS	2000/10/03 00:42:55
@@ -66,6 +66,11 @@
 
 Changes to the standard library:
 
+* We've added new predicates map__foldl2, tree234__foldl2 and aggregate2.
+
+* We've added function versions of solutions, solutions_set,
+  aggregate, map__search, map__insert and map__update.
+
 * We've added a pretty printing module, `pprint', to the standard library.
 
 * We've added a new function to the Mercury standard library:
Index: library/map.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/map.m,v
retrieving revision 1.75
diff -u -r1.75 map.m
--- library/map.m	2000/08/04 02:01:27	1.75
+++ library/map.m	2000/10/03 00:42:56
@@ -199,13 +199,28 @@
 :- pred map__remove_smallest(map(K, V), K, V, map(K, V)).
 :- mode map__remove_smallest(in, out, out, out) is semidet.
 
-	% Perform an inorder tranversal of the map, applying
+	% Perform an inorder traversal of the map, applying
 	% an accumulator predicate for each key-value pair.
 :- pred map__foldl(pred(K, V, T, T), map(K, V), T, T).
 :- mode map__foldl(pred(in, in, in, out) is det, in, in, out) is det.
 :- mode map__foldl(pred(in, in, in, out) is semidet, in, in, out) is semidet.
 :- mode map__foldl(pred(in, in, di, uo) is det, in, di, uo) is det.
 
+	% Perform an inorder traversal of the map, applying
+	% an accumulator predicate with two accumulators for
+	% each key-value pair.
+	% (Although no more expressive than map__foldl, this is often
+	% a more convenient format, and a little more efficient).
+:- pred map__foldl2(pred(K, V, T, T, U, U), map(K, V), T, T, U, U).
+:- mode map__foldl2(pred(in, in, in, out, in, out) is det, 
+		in, in, out, in, out) is det.
+:- mode map__foldl2(pred(in, in, in, out, in, out) is semidet, 
+		in, in, out, in, out) is semidet.
+:- mode map__foldl2(pred(in, in, in, out, di, uo) is det,
+		in, in, out, di, uo) is det.
+:- mode map__foldl2(pred(in, in, di, uo, di, uo) is det,
+		in, di, uo, di, uo) is det.
+
 	% Apply a transformation predicate to all the values
 	% in a map.
 :- pred map__map_values(pred(K, V, W), map(K, V), map(K, W)).
@@ -491,6 +506,11 @@
 
 %-----------------------------------------------------------------------------%
 
+map__foldl2(Pred, Map, Acc0, Acc) -->
+	tree234__foldl2(Pred, Map, Acc0, Acc).
+
+%-----------------------------------------------------------------------------%
+
 map__map_values(Pred, Map0, Map) :-
 	tree234__map_values(Pred, Map0, Map).
 
@@ -621,8 +641,12 @@
 :- func map__init = map(K, V).
 :- mode map__init = uo is det.
 
+:- func map__search(map(K,V), K) = V is semidet.
+
 :- func map__lookup(map(K,V), K) = V.
 
+:- func map__insert(map(K,V), K, V) = map(K,V) is semidet.
+
 :- func map__det_insert(map(K,V), K, V) = map(K,V).
 
 :- func map__det_insert_from_corresponding_lists(map(K,V), list(K), list(V)) =
@@ -630,6 +654,8 @@
 
 :- func map__det_insert_from_assoc_list(map(K,V), assoc_list(K, V)) = map(K,V).
 
+:- func map__update(map(K,V), K, V) = map(K,V) is semidet.
+
 :- func map__det_update(map(K,V), K, V) = map(K,V).
 
 :- func map__set(map(K,V), K, V) = map(K,V).
@@ -688,9 +714,15 @@
 map__init = M :-
 	map__init(M).
 
+map__search(M, K) = V :-
+	map__search(M, K, V).
+
 map__lookup(M, K) = V :-
 	map__lookup(M, K, V).
 
+map__insert(M1, K, V) = M2 :-
+	map__insert(M1, K, V, M2).
+
 map__det_insert(M1, K, V) = M2 :-
 	map__det_insert(M1, K, V, M2).
 
@@ -699,6 +731,9 @@
 
 map__det_insert_from_assoc_list(M1, AL) = M2 :-
 	map__det_insert_from_assoc_list(M1, AL, M2).
+
+map__update(M1, K, V) = M2 :-
+	map__update(M1, K, V, M2).
 
 map__det_update(M1, K, V) = M2 :-
 	map__det_update(M1, K, V, M2).
Index: library/tree234.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/tree234.m,v
retrieving revision 1.31
diff -u -r1.31 tree234.m
--- library/tree234.m	2000/09/14 08:19:07	1.31
+++ library/tree234.m	2000/10/03 00:42:56
@@ -105,6 +105,17 @@
 		is semidet.
 :- mode tree234__foldl(pred(in, in, di, uo) is det, in, di, uo) is det.
 
+:- pred tree234__foldl2(pred(K, V, T, T, U, U), tree234(K, V), T, T, U, U).
+:- mode tree234__foldl2(pred(in, in, in, out, in, out) is det, 
+		in, in, out, in, out) is det.
+:- mode tree234__foldl2(pred(in, in, in, out, in, out) is semidet, 
+		in, in, out, in, out) is semidet.
+:- mode tree234__foldl2(pred(in, in, in, out, di, uo) is det,
+		in, in, out, di, uo) is det.
+:- mode tree234__foldl2(pred(in, in, di, uo, di, uo) is det,
+		in, di, uo, di, uo) is det.
+
+
 :- pred tree234__map_values(pred(K, V, W), tree234(K, V), tree234(K, W)).
 :- mode tree234__map_values(pred(in, in, out) is det, in, out) is det.
 :- mode tree234__map_values(pred(in, in, out) is semidet, in, out) is semidet.
@@ -2439,6 +2450,26 @@
 	tree234__foldl(Pred, T2, Acc4, Acc5),
 	call(Pred, K2, V2, Acc5, Acc6),
 	tree234__foldl(Pred, T3, Acc6, Acc).
+
+tree234__foldl2(_Pred, empty, A, A) --> [].
+tree234__foldl2(Pred, two(K, V, T0, T1), A0, A) -->
+	tree234__foldl2(Pred, T0, A0, A1),
+	call(Pred, K, V, A1, A2),
+	tree234__foldl2(Pred, T1, A2, A).
+tree234__foldl2(Pred, three(K0, V0, K1, V1, T0, T1, T2), A0, A) -->
+	tree234__foldl2(Pred, T0, A0, A1),
+	call(Pred, K0, V0, A1, A2),
+	tree234__foldl2(Pred, T1, A2, A3),
+	call(Pred, K1, V1, A3, A4),
+	tree234__foldl2(Pred, T2, A4, A).
+tree234__foldl2(Pred, four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3), A0, A) -->
+	tree234__foldl2(Pred, T0, A0, A1),
+	call(Pred, K0, V0, A1, A2),
+	tree234__foldl2(Pred, T1, A2, A3),
+	call(Pred, K1, V1, A3, A4),
+	tree234__foldl2(Pred, T2, A4, A5),
+	call(Pred, K2, V2, A5, A6),
+	tree234__foldl2(Pred, T3, A6, A).
 
 %------------------------------------------------------------------------------%
 
Index: library/std_util.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/std_util.m,v
retrieving revision 1.199
diff -u -r1.199 std_util.m
--- library/std_util.m	2000/09/25 04:37:19	1.199
+++ library/std_util.m	2000/10/03 00:42:58
@@ -156,6 +156,26 @@
 :- mode aggregate(pred(out) is nondet, pred(in, in, out) is det,
 		in, out) is det.
 
+	% aggregate2/6 generates all the solutions to a predicate,
+	% sorts them and removes duplicates, then applies an accumulator
+	% predicate to each solution in turn:
+	%
+	% aggregate2(Generator, Accumulator, AccA0, AccA, AccB0, AccB) <=>
+	%	solutions(Generator, Solutions),
+	%	list__foldl2(Accumulator, Solutions, AccA0, AccA, AccB0, AccB).
+	%
+
+:- pred aggregate2(pred(T), pred(T, U, U, V, V), U, U, V, V).
+:- mode aggregate2(pred(out) is multi, pred(in, in, out, in, out) is det,
+		in, out, in, out) is det.
+:- mode aggregate2(pred(out) is multi, pred(in, in, out, di, uo) is det,
+		in, out, di, uo) is det.
+:- mode aggregate2(pred(out) is nondet, pred(in, in, out, di, uo) is det,
+		in, out, di, uo) is det.
+:- mode aggregate2(pred(out) is nondet, pred(in, in, out, in, out) is det,
+		in, out, in, out) is det.
+
+
 	% unsorted_aggregate/4 generates all the solutions to a predicate
 	% and applies an accumulator predicate to each solution in turn.
 	% Declaratively, the specification is as follows:
@@ -958,6 +978,10 @@
 	solutions(Generator, Solutions),
 	list__foldl(Accumulator, Solutions, Acc0, Acc).
 
+aggregate2(Generator, Accumulator, Acc0, Acc) -->
+	{ solutions(Generator, Solutions) },
+	list__foldl2(Accumulator, Solutions, Acc0, Acc).
+
 unsorted_aggregate(Generator, Accumulator, Acc0, Acc) :-
 	builtin_aggregate(Generator, Accumulator, Acc0, Acc1),
 	cc_multi_equal(Acc1, Acc).
@@ -3550,6 +3574,20 @@
     %
 :- func id(T) = T.
 
+:- func solutions(pred(T)) = list(T).
+:- mode solutions(pred(out) is multi) = out is det.
+:- mode solutions(pred(out) is nondet) = out is det.
+
+:- func solutions_set(pred(T)) = set(T).
+:- mode solutions_set(pred(out) is multi) = out is det.
+:- mode solutions_set(pred(out) is nondet) = out is det.
+
+:- func aggregate(pred(T), func(T, U) = U, U) = U.
+:- mode aggregate(pred(out) is multi, func(in, in) = out is det,
+		in) = out is det.
+:- mode aggregate(pred(out) is nondet, func(in, in) = out is det,
+		in) = out is det.
+
 % ---------------------------------------------------------------------------- %
 % ---------------------------------------------------------------------------- %
 
@@ -3574,3 +3612,11 @@
 	not P(X).
 
 id(X) = X.
+
+solutions(P) = S :- solutions(P, S).
+
+solutions_set(P) = S :- solutions_set(P, S).
+
+aggregate(P, F, Acc0) = Acc :-
+	aggregate(P, (pred(X::in, A0::in, A::out) is det :- A = F(X, A0)),
+		Acc0, Acc).
-- 
David Overton      Department of Computer Science & Software Engineering
PhD Student        The University of Melbourne, Victoria 3010, Australia
+61 3 8344 9159    http://www.cs.mu.oz.au/~dmo
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------