[m-rev.] for review: list.negated_filter

[Zoltan Somogyi]

This avoids the need for auxiliary predicates in several places,
e.g. in the deep profiler. That diff will come later. The main
thing to review is the predicate's name.

Zoltan.

library/list.m:
	Add list.negated_filter.

	Reimplement list.filter/3 to avoid constructing the list of elements
	for which the test predicate fails.

NEWS:
	Mention the new predicate.

Index: NEWS
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/NEWS,v
retrieving revision 1.494
diff -u -b -r1.494 NEWS
--- NEWS	7 Aug 2008 01:16:18 -0000	1.494
+++ NEWS	11 Aug 2008 03:19:25 -0000
@@ -89,6 +89,7 @@
 	list.map_corresponding_foldl2/8
 	list.map_corresponding_foldl3/10
 	list.map_corresponding3_foldl/7
+	list.negated_filter/3
 	list.foldl3_corresponding/9
 	list.foldl_corresponding3/6
 	list.foldl2_corresponding3/8
cvs diff: Diffing library
Index: library/list.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/list.m,v
retrieving revision 1.173
diff -u -b -r1.173 list.m
--- library/list.m	31 Jul 2008 06:34:40 -0000	1.173
+++ library/list.m	11 Aug 2008 03:18:41 -0000
@@ -1249,6 +1249,15 @@
 :- func list.filter(pred(X)::in(pred(in) is semidet), list(X)::in)
     = (list(X)::out) is det.
 
+    % list.negated_filter(Pred, List, FalseList) takes a closure with one
+    % input argument and for each member of List `X', calls the closure.
+    % Iff Pred(X) is false, then X is included in FalseList.
+    %
+:- pred list.negated_filter(pred(X)::in(pred(in) is semidet), list(X)::in,
+    list(X)::out) is det.
+:- func list.negated_filter(pred(X)::in(pred(in) is semidet), list(X)::in)
+    = (list(X)::out) is det.
+
     % list.filter(Pred, List, TrueList, FalseList) takes a closure with one
     % input argument and for each member of List `X', calls the closure.
     % Iff Pred(X) is true, then X is included in TrueList.
@@ -2338,8 +2347,23 @@
     not P(X),
     list.all_false(P, Xs).
 
-list.filter(P, Xs, Ys) :-
-    list.filter(P, Xs, Ys, _).
+list.filter(_, [],  []).
+list.filter(P, [H | T], True) :-
+    list.filter(P, T, TrueTail),
+    ( P(H) ->
+        True = [H | TrueTail]
+    ;
+        True = TrueTail
+    ).
+
+list.negated_filter(_, [],  []).
+list.negated_filter(P, [H | T], False) :-
+    list.negated_filter(P, T, FalseTail),
+    ( P(H) ->
+        False = FalseTail
+    ;
+        False = [H | FalseTail]
+    ).
 
 list.filter(_, [],  [], []).
 list.filter(P, [H | T], True, False) :-
@@ -2617,8 +2641,11 @@
     P = ( pred(X::in, Y::in, Z::out) is det :- Z = F(X, Y) ),
     list.foldr(P, Xs, A, B).
 
-list.filter(P, Xs) = Ys :-
-    list.filter(P, Xs, Ys).
+list.filter(P, Xs) = Trues :-
+    list.filter(P, Xs, Trues).
+
+list.negated_filter(P, Xs) = Falses :-
+    list.negated_filter(P, Xs, Falses).
 
 list.filter_map(F, Xs) = Ys :-
     P = ( pred(X::in, Y::out) is semidet :- Y = F(X) ),
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------