[m-rev.] for post-commit review: more operations on cords
Zoltan Somogyi
zs at csse.unimelb.edu.au
Mon Jan 12 13:28:14 AEDT 2009
library/cord.m:
Add new predicates to operate on cords, for use in the modules above.
NEWS:
Mention the new predicates on cords.
Index: NEWS
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/NEWS,v
retrieving revision 1.498
diff -u -b -r1.498 NEWS
--- NEWS 2 Jan 2009 03:12:02 -0000 1.498
+++ NEWS 10 Jan 2009 09:24:38 -0000
@@ -218,8 +218,9 @@
* We have added the predicates `dir.current_directory',
`dir.relative_path_name_from_components'.
-* We have added the predicates split_last, get_first, get_last and
- cord_list_to_cord to the cord module.
+* We have added the predicates rev_list, split_last, get_first, get_last,
+ filter, foldl_pred, foldr_pred, map_foldl, map_foldl[23], cord_list_to_cord
+ and cord_list_to_list to the cord module.
* We have added two predicates that are useful for custom term construction:
construct.find_functor/5
cvs diff: Diffing library
Index: library/cord.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/cord.m,v
retrieving revision 1.13
diff -u -b -r1.13 cord.m
--- library/cord.m 6 Jan 2009 03:56:53 -0000 1.13
+++ library/cord.m 10 Jan 2009 14:55:04 -0000
@@ -49,6 +49,10 @@
%
:- func list(cord(T)) = list(T).
+ % rev_list(Cord) = list.reverse(list(Cord).
+ %
+:- func rev_list(cord(T)) = list(T).
+
% The unique representation for the empty cord:
%
% list(empty) = []
@@ -87,6 +91,10 @@
%
:- func cord_list_to_cord(list(cord(T))) = cord(T).
+ % Append together a list of cords, and return the result as a list.
+ %
+:- func cord_list_to_list(list(cord(T))) = list(T).
+
% head_tail(C0, X, C) => list(C0) = [X | list(C)]
% not head_tail(C0, _, _) => C0 = empty
% An O(n) operation, although traversing an entire cord with
@@ -126,13 +134,53 @@
:- pred map_pred(pred(T, U)::in(pred(in, out) is det),
cord(T)::in, cord(U)::out) is det.
+ % filter(Pred, Cord, TrueCord):
+ %
+ % Pred is a closure with one input argument.
+ % For each member X of Cord,
+ % - Pred(X) is true, then X is included in TrueCord.
+ %
+:- pred filter(pred(T)::in(pred(in) is semidet),
+ cord(T)::in, cord(T)::out) is det.
+
+ % filter(Pred, Cord, TrueCord, FalseCord):
+ %
+ % Pred is a closure with one input argument.
+ % For each member X of Cord,
+ % - Pred(X) is true, then X is included in TrueCord.
+ % - Pred(X) is false, then X is included in FalseCord.
+ %
+:- pred filter(pred(T)::in(pred(in) is semidet),
+ cord(T)::in, cord(T)::out, cord(T)::out) is det.
+
% foldl(F, C, A) = list.foldl(F, list(C), A).
%
:- func foldl(func(T, U) = U, cord(T), U) = U.
+:- pred foldl_pred(pred(T, U, U)::in(pred(in, in, out) is det), cord(T)::in,
+ U::in, U::out) is det.
% foldr(F, C, A) = list.foldr(F, list(C), A).
%
:- func foldr(func(T, U) = U, cord(T), U) = U.
+:- pred foldr_pred(pred(T, U, U)::in(pred(in, in, out) is det), cord(T)::in,
+ U::in, U::out) is det.
+
+ % map_foldl(P, CA, CB, !Acc):
+ %
+ % This predicate calls P on each element of the input cord, working
+ % left to right. Each call to P transforms an element of the input cord
+ % to the corresponding element of the output cord, and updates the
+ % accumulator(s).
+ %
+:- pred map_foldl(pred(A, B, C, C)::in(pred(in, out, in, out) is det),
+ cord(A)::in, cord(B)::out, C::in, C::out) is det.
+:- pred map_foldl2(pred(A, B, C, C, D, D)::
+ in(pred(in, out, in, out, in, out) is det),
+ cord(A)::in, cord(B)::out, C::in, C::out, D::in, D::out) is det.
+:- pred map_foldl3(pred(A, B, C, C, D, D, E, E)::
+ in(pred(in, out, in, out, in, out, in, out) is det),
+ cord(A)::in, cord(B)::out, C::in, C::out, D::in, D::out, E::in, E::out)
+ is det.
% equal(CA, CB) <=> list(CA) = list(CB).
% An O(n) operation where n = length(CA) + length(CB).
@@ -190,6 +238,10 @@
list(C) = list_2(C, []).
+ % list_2(C, L0) = L:
+ %
+ % L is the list of items in C appended in front of L0.
+ %
:- func list_2(cord(T), list(T)) = list(T).
list_2(nil, Xs) = Xs.
@@ -197,6 +249,29 @@
list_2(leaves(Ys), Xs) = Ys ++ Xs.
list_2(branch(CA, CB), Xs) = list_2(CA, list_2(CB, Xs)).
+rev_list(C) = rev_list_2(C, []).
+
+ % rev_list_2(C, L0) = L:
+ %
+ % L is the reverse list of items in C appended in front of L0.
+ %
+:- func rev_list_2(cord(T), list(T)) = list(T).
+
+rev_list_2(nil, Xs) = Xs.
+rev_list_2(leaf(Y), Xs) = [Y | Xs].
+rev_list_2(leaves(Ys), Xs) = list_reverse_2(Ys, Xs).
+rev_list_2(branch(CA, CB), Xs) = rev_list_2(CB, list_2(CA, Xs)).
+
+ % list_reverse_2(A, L0) = L:
+ %
+ % L is the reverse list of items in A appended in front of L0.
+ %
+:- func list_reverse_2(list(A), list(A)) = list(A).
+
+list_reverse_2([], L) = L.
+list_reverse_2([X | Xs], L0) =
+ list_reverse_2(Xs, [X | L0]).
+
%-----------------------------------------------------------------------------%
cons(X, C) = XC :-
@@ -238,6 +313,10 @@
cord_list_to_cord([HeadCord | TailCords]) =
HeadCord ++ cord_list_to_cord(TailCords).
+cord_list_to_list([]) = [].
+cord_list_to_list([HeadCord | TailCords]) =
+ list(HeadCord) ++ cord_list_to_list(TailCords).
+
%-----------------------------------------------------------------------------%
head_tail(leaf(X), X, nil).
@@ -363,11 +442,74 @@
%-----------------------------------------------------------------------------%
+filter(_P, nil, nil).
+filter(P, leaf(X), Trues) :-
+ ( P(X) ->
+ Trues = leaf(X)
+ ;
+ Trues = nil
+ ).
+filter(P, leaves(Xs), Trues) :-
+ list.filter(P, Xs, TrueList),
+ (
+ TrueList = [],
+ Trues = nil
+ ;
+ TrueList = [_ | _],
+ Trues = leaves(TrueList)
+ ).
+filter(P, branch(CA, CB), Trues) :-
+ filter(P, CA, CATrues),
+ filter(P, CB, CBTrues),
+ Trues = CATrues ++ CBTrues.
+
+filter(_P, nil, nil, nil).
+filter(P, leaf(X), Trues, Falses) :-
+ ( P(X) ->
+ Trues = leaf(X),
+ Falses = nil
+ ;
+ Trues = nil,
+ Falses = leaf(X)
+ ).
+filter(P, leaves(Xs), Trues, Falses) :-
+ list.filter(P, Xs, TrueList, FalseList),
+ (
+ TrueList = [],
+ Trues = nil
+ ;
+ TrueList = [_ | _],
+ Trues = leaves(TrueList)
+ ),
+ (
+ FalseList = [],
+ Falses = nil
+ ;
+ FalseList = [_ | _],
+ Falses = leaves(FalseList)
+ ).
+filter(P, branch(CA, CB), Trues, Falses) :-
+ filter(P, CA, CATrues, CAFalses),
+ filter(P, CB, CBTrues, CBFalses),
+ Trues = CATrues ++ CBTrues,
+ Falses = CAFalses ++ CBFalses.
+
+%-----------------------------------------------------------------------------%
+
foldl(_, nil, A) = A.
foldl(F, leaf(X), A) = F(X, A).
foldl(F, leaves(Xs), A) = foldl(F, Xs, A).
foldl(F, branch(CA, CB), A) = foldl(F, CB, foldl(F, CA, A)).
+foldl_pred(_P, nil, !A).
+foldl_pred(P, leaf(X), !A) :-
+ P(X, !A).
+foldl_pred(P, leaves(Xs), !A) :-
+ list.foldl(P, Xs, !A).
+foldl_pred(P, branch(XA, XB), !A) :-
+ foldl_pred(P, XA, !A),
+ foldl_pred(P, XB, !A).
+
%-----------------------------------------------------------------------------%
foldr(_, nil, A) = A.
@@ -375,6 +517,44 @@
foldr(F, leaves(Xs), A) = foldr(F, Xs, A).
foldr(F, branch(CA, CB), A) = foldr(F, CA, foldr(F, CB, A)).
+foldr_pred(_P, nil, !A).
+foldr_pred(P, leaf(X), !A) :-
+ P(X, !A).
+foldr_pred(P, leaves(Xs), !A) :-
+ list.foldr(P, Xs, !A).
+foldr_pred(P, branch(XA, XB), !A) :-
+ foldr_pred(P, XB, !A),
+ foldr_pred(P, XA, !A).
+
+%-----------------------------------------------------------------------------%
+
+map_foldl(_P, nil, nil, !A).
+map_foldl(P, leaf(X), leaf(Y), !A) :-
+ P(X, Y, !A).
+map_foldl(P, leaves(Xs), leaves(Ys), !A) :-
+ list.map_foldl(P, Xs, Ys, !A).
+map_foldl(P, branch(XA, XB), branch(YA, YB), !A) :-
+ map_foldl(P, XA, YA, !A),
+ map_foldl(P, XB, YB, !A).
+
+map_foldl2(_P, nil, nil, !A, !B).
+map_foldl2(P, leaf(X), leaf(Y), !A, !B) :-
+ P(X, Y, !A, !B).
+map_foldl2(P, leaves(Xs), leaves(Ys), !A, !B) :-
+ list.map_foldl2(P, Xs, Ys, !A, !B).
+map_foldl2(P, branch(XA, XB), branch(YA, YB), !A, !B) :-
+ map_foldl2(P, XA, YA, !A, !B),
+ map_foldl2(P, XB, YB, !A, !B).
+
+map_foldl3(_P, nil, nil, !A, !B, !C).
+map_foldl3(P, leaf(X), leaf(Y), !A, !B, !C) :-
+ P(X, Y, !A, !B, !C).
+map_foldl3(P, leaves(Xs), leaves(Ys), !A, !B, !C) :-
+ list.map_foldl3(P, Xs, Ys, !A, !B, !C).
+map_foldl3(P, branch(XA, XB), branch(YA, YB), !A, !B, !C) :-
+ map_foldl3(P, XA, YA, !A, !B, !C),
+ map_foldl3(P, XB, YB, !A, !B, !C).
+
%-----------------------------------------------------------------------------%
equal(CA, CB) :-
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------
More information about the reviews
mailing list