[m-dev.] for review: new library preds

[Zoltan Somogyi]

For review by anyone.

Add several useful library predicates.

library/assoc_list.m:
	Add assoc_list__map_values.

library/list.m:
	Add list__all_true and list__all_false.

library/set.m:
	Add set__non_empty (for use in higher-order goals without a lambda for
	the negation) and set__filter.

library/map.m:
library/tree234.m:
	Add map__map_foldl and tree234__map_foldl.

Zoltan.

cvs diff: Diffing .
Index: assoc_list.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/assoc_list.m,v
retrieving revision 1.10
diff -u -b -r1.10 assoc_list.m
--- assoc_list.m	1999/10/30 04:15:57	1.10
+++ assoc_list.m	2000/07/17 06:07:24
@@ -61,6 +61,9 @@
 	assoc_list(K, V)).
 :- mode assoc_list__remove(in, in, out, out) is semidet.
 
+:- func assoc_list__map_values(func(K, V) = W, assoc_list(K, V))
+	= assoc_list(K, W).
+
 %-----------------------------------------------------------------------------%
 
 :- implementation.
@@ -136,7 +139,8 @@
 
 :- func assoc_list__reverse_members(assoc_list(K, V)) = assoc_list(V, K).
 
-:- func assoc_list__from_corresponding_lists(list(K), list(V)) = assoc_list(K,V).
+:- func assoc_list__from_corresponding_lists(list(K), list(V))
+	= assoc_list(K,V).
 
 :- func assoc_list__keys(assoc_list(K, V)) = list(K).
 
@@ -158,5 +162,8 @@
 
 assoc_list__values(AL) = Vs :-
 	assoc_list__values(AL, Vs).
-
 
+assoc_list__map_values(_F, []) = [].
+assoc_list__map_values(F, [K - V0 | KVs0]) = [K - V | KVs] :-
+	V = apply(F, K, V0),
+	KVs = assoc_list__map_values(F, KVs0).
Index: list.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/list.m,v
retrieving revision 1.91
diff -u -b -r1.91 list.m
--- list.m	2000/04/12 09:48:24	1.91
+++ list.m	2000/07/17 06:07:25
@@ -417,7 +417,7 @@
 	% list__map_foldl(Pred, InList, OutList, Start, End) calls Pred
 	% with an accumulator (with the initial value of Start) on
 	% each element of InList (working left-to-right) to transform
-	% InList into OutList.  The final value of the acumulator is
+	% InList into OutList.  The final value of the accumulator is
 	% returned in End.
 :- pred list__map_foldl(pred(X, Y, Z, Z), list(X), list(Y), Z, Z).
 :- mode list__map_foldl(pred(in, out, di, uo) is det, in, out, di, uo)
@@ -466,6 +466,16 @@
 :- pred list__takewhile(pred(T), list(T), list(T), list(T)).
 :- mode list__takewhile(pred(in) is semidet, in, out, out) is det.
 
+	% list__all_true(Predicate, List) succeeds if and only if
+	% Predicate succeeds on all the elements of List.
+:- pred list__all_true(pred(T), list(T)).
+:- mode list__all_true(pred(in) is semidet, in) is semidet.
+
+	% list__all_false(Predicate, List) succeeds if and only if
+	% Predicate fails on all the elements of List.
+:- pred list__all_false(pred(T), list(T)).
+:- mode list__all_false(pred(in) is semidet, in) is semidet.
+
 %-----------------------------------------------------------------------------%
 
 	% list__sort(Compare, Unsorted, Sorted) is true iff Sorted is a
@@ -500,7 +510,6 @@
 :- mode list__merge_and_remove_dups(pred(in, in, out) is det,
 	in, in, out) is det.
 
-
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 
@@ -1053,6 +1062,16 @@
 		Ins = [],
 		Outs = [X|Xs]
 	).
+
+list__all_true(_, []).
+list__all_true(P, [X | Xs]) :-
+	call(P, X),
+	list__all_true(P, Xs).
+
+list__all_false(_, []).
+list__all_false(P, [X | Xs]) :-
+	\+ call(P, X),
+	list__all_false(P, Xs).
 
 list__sort_and_remove_dups(P, L0, L) :-
 	list__sort(P, L0, L1),
Index: map.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/map.m,v
retrieving revision 1.73
diff -u -b -r1.73 map.m
--- map.m	2000/03/31 01:05:47	1.73
+++ map.m	2000/07/17 06:07:25
@@ -213,6 +213,14 @@
 :- mode map__map_values(pred(in, in, out) is det, in, out) is det.
 :- mode map__map_values(pred(in, in, out) is semidet, in, out) is semidet.
 
+	% Apply a transformation predicate to all the values
+	% in a map, while continuously updating an accumulator.
+:- pred map__map_foldl(pred(K, V, W, A, A), map(K, V), map(K, W), A, A).
+:- mode map__map_foldl(pred(in, in, out, in, out) is det, in, out, in, out)
+	is det.
+:- mode map__map_foldl(pred(in, in, out, in, out) is semidet, in, out, in, out)
+	is semidet. 
+
 	% 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 value in the final map by applying the supplied
@@ -487,6 +495,9 @@
 map__map_values(Pred, Map0, Map) :-
 	tree234__map_values(Pred, Map0, Map).
 
+map__map_foldl(Pred, Map0, Map, Acc0, Acc) :-
+	tree234__map_foldl(Pred, Map0, Map, Acc0, Acc).
+
 %-----------------------------------------------------------------------------%
 
 map__intersect(CommonPred, Map1, Map2, Common) :-
@@ -767,4 +778,3 @@
 map__det_union(F, M1, M2) = M3 :-
 	P = ( pred(X::in, Y::in, Z::out) is semidet :- Z = F(X, Y) ),
 	map__det_union(P, M1, M2, M3).
-
Index: set.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/set.m,v
retrieving revision 1.51
diff -u -b -r1.51 set.m
--- set.m	1999/07/07 15:19:41	1.51
+++ set.m	2000/07/17 06:07:26
@@ -74,6 +74,9 @@
 :- pred set__empty(set(T)).
 :- mode set__empty(in) is semidet.
 
+:- pred set__non_empty(set(T)).
+:- mode set__non_empty(in) is semidet.
+
 	% `set__subset(SetA, SetB)' is true iff `SetA' is a subset of `SetB'.
 
 :- pred set__subset(set(T), set(T)).
@@ -232,6 +235,9 @@
 
 :- func set__map(func(T1) = T2, set(T1)) = set(T2).
 
+:- func set__filter(pred(T1), set(T1)) = set(T1).
+:- mode set__filter(pred(in) is semidet, in) = out is det.
+
 :- func set__filter_map(func(T1) = T2, set(T1)) = set(T2).
 :- mode set__filter_map(func(in) = out is semidet, in) = out is det.
 
@@ -272,6 +278,9 @@
 set__empty(Set) :-
 	set_ordlist__empty(Set).
 
+set__non_empty(Set) :-
+	\+ set_ordlist__empty(Set).
+
 set__subset(SetA, SetB) :-
 	set_ordlist__subset(SetA, SetB).
 
@@ -369,6 +378,9 @@
 
 set__map(F, S1) = S2 :-
 	S2 = set__list_to_set(list__map(F, set__to_sorted_list(S1))).
+
+set__filter(P, S1) = S2 :-
+	S2 = set__list_to_set(list__filter(P, set__to_sorted_list(S1))).
 
 set__filter_map(PF, S1) = S2 :-
 	S2 = set__list_to_set(list__filter_map(PF, set__to_sorted_list(S1))).
Index: tree234.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/tree234.m,v
retrieving revision 1.28
diff -u -b -r1.28 tree234.m
--- tree234.m	2000/03/28 03:41:11	1.28
+++ tree234.m	2000/07/17 06:07:27
@@ -104,6 +104,13 @@
 :- 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.
 
+:- pred tree234__map_foldl(pred(K, V, W, A, A), tree234(K, V), tree234(K, W),
+	A, A).
+:- mode tree234__map_foldl(pred(in, in, out, in, out) is det,
+	in, out, in, out) is det.
+:- mode tree234__map_foldl(pred(in, in, out, in, out) is semidet,
+	in, out, in, out) is semidet.
+
 %------------------------------------------------------------------------------%
 %------------------------------------------------------------------------------%
 
@@ -2455,6 +2462,34 @@
 	tree234__map_values(Pred, LMid0, LMid),
 	tree234__map_values(Pred, RMid0, RMid),
 	tree234__map_values(Pred, Right0, Right).
+
+%------------------------------------------------------------------------------%
+
+tree234__map_foldl(_Pred, empty, empty, A, A).
+tree234__map_foldl(Pred, Tree0, Tree, A0, A) :-
+	Tree0 = two(K0, V0, Left0, Right0),
+	Tree  = two(K0, W0, Left, Right),
+	tree234__map_foldl(Pred, Left0, Left, A0, A1),
+	call(Pred, K0, V0, W0, A1, A2),
+	tree234__map_foldl(Pred, Right0, Right, A2, A).
+tree234__map_foldl(Pred, Tree0, Tree, A0, A) :-
+	Tree0 = three(K0, V0, K1, V1, Left0, Middle0, Right0),
+	Tree  = three(K0, W0, K1, W1, Left, Middle, Right),
+	tree234__map_foldl(Pred, Left0, Left, A0, A1),
+	call(Pred, K0, V0, W0, A1, A2),
+	tree234__map_foldl(Pred, Middle0, Middle, A2, A3),
+	call(Pred, K1, V1, W1, A3, A4),
+	tree234__map_foldl(Pred, Right0, Right, A4, A).
+tree234__map_foldl(Pred, Tree0, Tree, A0, A) :-
+	Tree0 = four(K0, V0, K1, V1, K2, V2, Left0, LMid0, RMid0, Right0),
+	Tree  = four(K0, W0, K1, W1, K2, W2, Left, LMid, RMid, Right),
+	tree234__map_foldl(Pred, Left0, Left, A0, A1),
+	call(Pred, K0, V0, W0, A1, A2),
+	tree234__map_foldl(Pred, LMid0, LMid, A2, A3),
+	call(Pred, K1, V1, W1, A3, A4),
+	tree234__map_foldl(Pred, RMid0, RMid, A4, A5),
+	call(Pred, K2, V2, W2, A5, A6),
+	tree234__map_foldl(Pred, Right0, Right, A6, A).
 
 %------------------------------------------------------------------------------%
 
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------