[m-rev.] diff: two new library predicates

[Zoltan Somogyi]

They are used by the term size profiling transformation, but I am sending
this separately to reduce the size of that diff a bit.

library/list.m:
	Add map2_foldl, a variant of map_foldl.

library/map.m:
	Add a new variant predicate to compute the common subset of two maps.

NEWS:
	Mention the new library predicates.

Zoltan.

Index: NEWS
===================================================================
RCS file: /home/mercury1/repository/mercury/NEWS,v
retrieving revision 1.313
diff -u -b -r1.313 NEWS
--- NEWS	22 May 2003 03:54:37 -0000	1.313
+++ NEWS	23 May 2003 05:33:35 -0000
@@ -91,6 +91,10 @@
 
 * We've added a new library module, `array2d'.
 
+* We've added a new predicate, list__map2_foldl, to list.m.
+
+* We've added a new predicate, map__common_subset, to map.m.
+
 * We've added a predicate, map_fold, to set.m.
 
 * We've added a predicate, expand_braces, to dir.m.
Index: library/list.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/list.m,v
retrieving revision 1.111
diff -u -b -r1.111 list.m
--- library/list.m	3 Feb 2003 05:19:29 -0000	1.111
+++ library/list.m	24 Mar 2003 08:19:04 -0000
@@ -580,6 +580,18 @@
 :- mode list__map_foldl(pred(in, out, in, out) is nondet, in, out, in, out)
 		is nondet.
 
+	% Same as list__map_foldl, but with two mapped outputs.
+:- pred list__map2_foldl(pred(X, Y1, Y2, Z, Z), list(X), list(Y1), list(Y2),
+		Z, Z).
+:- mode list__map2_foldl(pred(in, out, out, di, uo) is det, in, out, out,
+		di, uo) is det.
+:- mode list__map2_foldl(pred(in, out, out, in, out) is det, in, out, out,
+		in, out) is det.
+:- mode list__map2_foldl(pred(in, out, out, in, out) is semidet, in, out, out,
+		in, out) is semidet.
+:- mode list__map2_foldl(pred(in, out, out, in, out) is nondet, in, out, out,
+		in, out) is nondet.
+
 	% Same as list__map_foldl, but with two accumulators.
 :- pred list__map_foldl2(pred(X, Y, A, A, B, B), list(X), list(Y), A, A, B, B).
 :- mode list__map_foldl2(pred(in, out, in, out, di, uo) is det,
@@ -1356,6 +1368,12 @@
 list__map_foldl(P, [H0 | T0], [H | T]) -->
 	call(P, H0, H),
 	list__map_foldl(P, T0, T).
+
+list__map2_foldl(_, [], [], []) -->
+	[].
+list__map2_foldl(P, [H0 | T0], [H1 | T1], [H2 | T2]) -->
+	call(P, H0, H1, H2),
+	list__map2_foldl(P, T0, T1, T2).
 
 list__map_foldl2(_, [], [], A, A) --> [].
 list__map_foldl2(P, [H0 | T0], [H | T], A0, A) -->
Index: library/map.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/map.m,v
retrieving revision 1.81
diff -u -b -r1.81 map.m
--- library/map.m	19 Aug 2002 06:33:16 -0000	1.81
+++ library/map.m	26 May 2003 10:00:08 -0000
@@ -337,6 +337,21 @@
 :- func map__det_intersect(func(V, V) = V, map(K, V), map(K, V)) = map(K, V).
 :- mode map__det_intersect(func(in, in) = out is semidet, in, in) = out is det.
 
+	% Given two maps M1 and M2, create a third map M3 that has only the
+	% keys that occur in both M1 and M2. For keys that occur in both M1
+	% and M2, compute the corresponding values. If they are the same,
+	% include the key/value pair in M3. If they differ, do not include the
+	% key in M3.
+	%
+	% This predicate effectively considers the input maps to be sets of
+	% key/value pairs, computes the intersection of those two sets, and
+	% returns the map corresponding to the intersection.
+	%
+	% map__common_subset is very similar to map__intersect, but can succeed
+	% even with an output map that does not contain an entry for a key
+	% value that occurs in both input maps.
+:- func map__common_subset(map(K, V), map(K, V)) = map(K, V).
+
 	% Given two maps M1 and M2, create a third map M3 that all the keys
 	% that occur in either M1 and M2. For keys that occur in both M1
 	% and M2, compute the value in the final map by applying the supplied
@@ -356,7 +371,6 @@
 :- func map__det_union(func(V, V) = V, map(K, V), map(K, V)) = map(K, V).
 :- mode map__det_union(func(in, in) = out is semidet, in, in) = out is det.
 
-
 	% Field selection for maps.
 
 	% Map ^ elem(Key) = map__search(Map, Key).
@@ -365,7 +379,6 @@
 	% Map ^ det_elem(Key) = map__lookup(Map, Key).
 :- func map__det_elem(K, map(K, V)) = V. 
 
-
 	% Field update for maps.
 
 	% (Map ^ elem(Key) := Value) = map__set(Map, Key, Value).
@@ -731,6 +744,54 @@
 		Common = CommonPrime
 	;
 		error("map__det_intersect: map__intersect failed")
+	).
+
+%-----------------------------------------------------------------------------%
+
+map__common_subset(Map1, Map2) = Common :-
+	map__to_sorted_assoc_list(Map1, AssocList1),
+	map__to_sorted_assoc_list(Map2, AssocList2),
+	map__init(Common0),
+	map__common_subset_2(AssocList1, AssocList2, Common0) = Common.
+
+:- func map__common_subset_2(assoc_list(K, V), assoc_list(K, V),
+	map(K, V)) = map(K, V).
+
+map__common_subset_2(AssocList1, AssocList2, Common0) = Common :-
+	(
+		AssocList1 = [],
+		AssocList2 = [],
+		Common = Common0
+	;
+		AssocList1 = [_ | _],
+		AssocList2 = [],
+		Common = Common0
+	;
+		AssocList1 = [],
+		AssocList2 = [_ | _],
+		Common = Common0
+	;
+		AssocList1 = [Key1 - Value1 | AssocTail1],
+		AssocList2 = [Key2 - Value2 | AssocTail2],
+		compare(R, Key1, Key2),
+		(
+			R = (=),
+			( Value1 = Value2 ->
+				map__det_insert(Common0, Key1, Value1, Common1)
+			;
+				Common1 = Common0
+			),
+			Common = map__common_subset_2(AssocTail1, AssocTail2,
+				Common1)
+		;
+			R = (<),
+			Common = map__common_subset_2(AssocTail1, AssocList2,
+				Common0)
+		;
+			R = (>),
+			Common = map__common_subset_2(AssocList1, AssocTail2,
+				Common0)
+		)
 	).
 
 %-----------------------------------------------------------------------------%
--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------