[m-dev.] For review: add foldr family to map and tree234

[Ralph Becket]

Estimated hours taken: 2
Branches: main

Add the foldr family to map and tree234.

library/map.m:
library/tree234.m:
	Added the foldr family.

tests/hard_coded/Mmakefile:
tests/hard_coded/map_fold.exp:
tests/hard_coded/map_fold.m:
	Add a test case for map.foldl/foldr.

Index: library/map.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/map.m,v
retrieving revision 1.109
diff -u -r1.109 map.m
--- library/map.m	6 Feb 2007 05:55:57 -0000	1.109
+++ library/map.m	13 Jul 2007 02:57:03 -0000
@@ -294,6 +294,12 @@
 :- 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.
 
+:- func map.foldr(func(K, V, A) = A, map(K, V), A) = A.
+:- pred map.foldr(pred(K, V, A, A), map(K, V), A, A).
+:- mode map.foldr(pred(in, in, in, out) is det, in, in, out) is det.
+:- mode map.foldr(pred(in, in, in, out) is semidet, in, in, out) is semidet.
+:- mode map.foldr(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
@@ -309,6 +315,16 @@
 :- mode map.foldl2(pred(in, in, di, uo, di, uo) is det,
     in, di, uo, di, uo) is det.
 
+:- pred map.foldr2(pred(K, V, A, A, B, B), map(K, V), A, A, B, B).
+:- mode map.foldr2(pred(in, in, in, out, in, out) is det,
+    in, in, out, in, out) is det.
+:- mode map.foldr2(pred(in, in, in, out, in, out) is semidet,
+    in, in, out, in, out) is semidet.
+:- mode map.foldr2(pred(in, in, in, out, di, uo) is det,
+    in, in, out, di, uo) is det.
+:- mode map.foldr2(pred(in, in, di, uo, di, uo) is det,
+    in, di, uo, di, uo) is det.
+
     % Perform an inorder traversal of the map, applying an accumulator
     % predicate with three accumulators for each key-value pair.
     % (Although no more expressive than map.foldl, this is often
@@ -326,6 +342,18 @@
 :- mode map.foldl3(pred(in, in, di, uo, di, uo, di, uo) is det,
     in, di, uo, di, uo, di, uo) is det.
 
+:- pred map.foldr3(pred(K, V, A, A, B, B, C, C), map(K, V), A, A, B, B, C, C).
+:- mode map.foldr3(pred(in, in, in, out, in, out, in, out) is det,
+    in, in, out, in, out, in, out) is det.
+:- mode map.foldr3(pred(in, in, in, out, in, out, in, out) is semidet,
+    in, in, out, in, out, in, out) is semidet.
+:- mode map.foldr3(pred(in, in, in, out, in, out, di, uo) is det,
+    in, in, out, in, out, di, uo) is det.
+:- mode map.foldr3(pred(in, in, in, out, di, uo, di, uo) is det,
+    in, in, out, di, uo, di, uo) is det.
+:- mode map.foldr3(pred(in, in, di, uo, di, uo, di, uo) is det,
+    in, di, uo, di, uo, di, uo) is det.
+
     % Perform an inorder traversal of the map, applying an accumulator
     % predicate with four accumulators for each key-value pair.
     % (Although no more expressive than map.foldl, this is often
@@ -345,6 +373,21 @@
 :- mode map.foldl4(pred(in, in, di, uo, di, uo, di, uo, di, uo) is det,
     in, di, uo, di, uo, di, uo, di, uo) is det.
 
+:- pred map.foldr4(pred(K, V, A, A, B, B, C, C, D, D), map(K, V),
+    A, A, B, B, C, C, D, D).
+:- mode map.foldr4(pred(in, in, in, out, in, out, in, out, in, out) is det,
+    in, in, out, in, out, in, out, in, out) is det.
+:- mode map.foldr4(pred(in, in, in, out, in, out, in, out, in, out) is semidet,
+    in, in, out, in, out, in, out, in, out) is semidet.
+:- mode map.foldr4(pred(in, in, in, out, in, out, in, out, di, uo) is det,
+    in, in, out, in, out, in, out, di, uo) is det.
+:- mode map.foldr4(pred(in, in, in, out, in, out, di, uo, di, uo) is det,
+    in, in, out, in, out, di, uo, di, uo) is det.
+:- mode map.foldr4(pred(in, in, in, out, di, uo, di, uo, di, uo) is det,
+    in, in, out, di, uo, di, uo, di, uo) is det.
+:- mode map.foldr4(pred(in, in, di, uo, di, uo, di, uo, di, uo) is det,
+    in, di, uo, di, uo, di, uo, di, uo) is det.
+
     % Apply a transformation predicate to all the values in a map.
     %
 :- func map.map_values(func(K, V) = W, map(K, V)) = map(K, W).
@@ -836,6 +879,18 @@
 map.foldl4(Pred, Map, !A, !B, !C, !D) :-
     tree234.foldl4(Pred, Map, !A, !B, !C, !D).
 
+map.foldr(Pred, Map, !A) :-
+    tree234.foldr(Pred, Map, !A).
+
+map.foldr2(Pred, Map, !A, !B) :-
+    tree234.foldr2(Pred, Map, !A, !B).
+
+map.foldr3(Pred, Map, !A, !B, !C) :-
+    tree234.foldr3(Pred, Map, !A, !B, !C).
+
+map.foldr4(Pred, Map, !A, !B, !C, !D) :-
+    tree234.foldr4(Pred, Map, !A, !B, !C, !D).
+
 %-----------------------------------------------------------------------------%
 
 map.map_values(Pred, Map0, Map) :-
@@ -1098,6 +1153,10 @@
     P = (pred(W::in, X::in, Y::in, Z::out) is det :- Z = F(W, X, Y) ),
     map.foldl(P, M, A, B).
 
+map.foldr(F, M, A) = B :-
+    P = (pred(W::in, X::in, Y::in, Z::out) is det :- Z = F(W, X, Y) ),
+    map.foldr(P, M, A, B).
+
 map.map_values(F, M1) = M2 :-
     P = (pred(X::in, Y::in, Z::out) is det :- Z = F(X, Y) ),
     map.map_values(P, M1, M2).
Index: library/tree234.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/tree234.m,v
retrieving revision 1.57
diff -u -r1.57 tree234.m
--- library/tree234.m	6 Feb 2007 05:55:58 -0000	1.57
+++ library/tree234.m	13 Jul 2007 01:34:17 -0000
@@ -171,6 +171,54 @@
 :- mode tree234.foldl4(pred(in, in, di, uo, di, uo, di, uo, di, uo) is det,
 	in, di, uo, di, uo, di, uo, di, uo) is det.
 
+:- func tree234.foldr(func(K, V, A) = A, tree234(K, V), A) = A.
+
+:- pred tree234.foldr(pred(K, V, A, A), tree234(K, V), A, A).
+:- mode tree234.foldr(pred(in, in, in, out) is det, in, in, out) is det.
+:- mode tree234.foldr(pred(in, in, in, out) is semidet, in, in, out)
+    is semidet.
+:- mode tree234.foldr(pred(in, in, di, uo) is det, in, di, uo) is det.
+
+:- pred tree234.foldr2(pred(K, V, A, A, B, B), tree234(K, V), A, A, B, B).
+:- mode tree234.foldr2(pred(in, in, in, out, in, out) is det,
+    in, in, out, in, out) is det.
+:- mode tree234.foldr2(pred(in, in, in, out, in, out) is semidet,
+    in, in, out, in, out) is semidet.
+:- mode tree234.foldr2(pred(in, in, in, out, di, uo) is det,
+    in, in, out, di, uo) is det.
+:- mode tree234.foldr2(pred(in, in, di, uo, di, uo) is det,
+    in, di, uo, di, uo) is det.
+
+:- pred tree234.foldr3(pred(K, V, A, A, B, B, C, C), tree234(K, V),
+	A, A, B, B, C, C).
+:- mode tree234.foldr3(pred(in, in, in, out, in, out, in, out) is det,
+    in, in, out, in, out, in, out) is det.
+:- mode tree234.foldr3(pred(in, in, in, out, in, out, in, out) is semidet,
+    in, in, out, in, out, in, out) is semidet.
+:- mode tree234.foldr3(pred(in, in, in, out, in, out, di, uo) is det,
+    in, in, out, in, out, di, uo) is det.
+:- mode tree234.foldr3(pred(in, in, in, out, di, uo, di, uo) is det,
+    in, in, out, di, uo, di, uo) is det.
+:- mode tree234.foldr3(pred(in, in, di, uo, di, uo, di, uo) is det,
+    in, di, uo, di, uo, di, uo) is det.
+
+:- pred tree234.foldr4(pred(K, V, A, A, B, B, C, C, D, D), tree234(K, V),
+	A, A, B, B, C, C, D, D).
+:- mode tree234.foldr4(pred(in, in, in, out, in, out, in, out, in, out)
+	is det,
+	in, in, out, in, out, in, out, in, out) is det.
+:- mode tree234.foldr4(pred(in, in, in, out, in, out, in, out, in, out)
+	is semidet,
+	in, in, out, in, out, in, out, in, out) is semidet.
+:- mode tree234.foldr4(pred(in, in, in, out, in, out, in, out, di, uo) is det,
+	in, in, out, in, out, in, out, di, uo) is det.
+:- mode tree234.foldr4(pred(in, in, in, out, in, out, di, uo, di, uo) is det,
+	in, in, out, in, out, di, uo, di, uo) is det.
+:- mode tree234.foldr4(pred(in, in, in, out, di, uo, di, uo, di, uo) is det,
+	in, in, out, di, uo, di, uo, di, uo) is det.
+:- mode tree234.foldr4(pred(in, in, di, uo, di, uo, di, uo, di, uo) is det,
+	in, di, uo, di, uo, di, uo, di, uo) is det.
+
 :- func tree234.map_values(func(K, V) = W, tree234(K, V)) = tree234(K, W).
 
 :- pred tree234.map_values(pred(K, V, W), tree234(K, V), tree234(K, W)).
@@ -2510,6 +2558,90 @@
 
 %------------------------------------------------------------------------------%
 
+tree234.foldr(_Pred, empty, !A).
+tree234.foldr(Pred, two(K, V, T0, T1), !A) :-
+    tree234.foldr(Pred, T1, !A),
+    Pred(K, V, !A),
+    tree234.foldr(Pred, T0, !A).
+tree234.foldr(Pred, three(K0, V0, K1, V1, T0, T1, T2), !A) :-
+    tree234.foldr(Pred, T2, !A),
+    Pred(K1, V1, !A),
+    tree234.foldr(Pred, T1, !A),
+    Pred(K0, V0, !A),
+    tree234.foldr(Pred, T0, !A).
+tree234.foldr(Pred, four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3), !A) :-
+    tree234.foldr(Pred, T3, !A),
+    Pred(K2, V2, !A),
+    tree234.foldr(Pred, T2, !A),
+    Pred(K1, V1, !A),
+    tree234.foldr(Pred, T1, !A),
+    Pred(K0, V0, !A),
+    tree234.foldr(Pred, T0, !A).
+
+tree234.foldr2(_Pred, empty, !A, !B).
+tree234.foldr2(Pred, two(K, V, T0, T1), !A, !B) :-
+    tree234.foldr2(Pred, T1, !A, !B),
+    Pred(K, V, !A, !B),
+    tree234.foldr2(Pred, T0, !A, !B).
+tree234.foldr2(Pred, three(K0, V0, K1, V1, T0, T1, T2), !A, !B) :-
+    tree234.foldr2(Pred, T2, !A, !B),
+    Pred(K1, V1, !A, !B),
+    tree234.foldr2(Pred, T1, !A, !B),
+    Pred(K0, V0, !A, !B),
+    tree234.foldr2(Pred, T0, !A, !B).
+tree234.foldr2(Pred, four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3), !A, !B) :-
+    tree234.foldr2(Pred, T3, !A, !B),
+    Pred(K2, V2, !A, !B),
+    tree234.foldr2(Pred, T2, !A, !B),
+    Pred(K1, V1, !A, !B),
+    tree234.foldr2(Pred, T1, !A, !B),
+    Pred(K0, V0, !A, !B),
+    tree234.foldr2(Pred, T0, !A, !B).
+
+tree234.foldr3(_Pred, empty, !A, !B, !C).
+tree234.foldr3(Pred, two(K, V, T0, T1), !A, !B, !C) :-
+    tree234.foldr3(Pred, T1, !A, !B, !C),
+    Pred(K, V, !A, !B, !C),
+    tree234.foldr3(Pred, T0, !A, !B, !C).
+tree234.foldr3(Pred, three(K0, V0, K1, V1, T0, T1, T2), !A, !B, !C) :-
+    tree234.foldr3(Pred, T2, !A, !B, !C),
+    Pred(K1, V1, !A, !B, !C),
+    tree234.foldr3(Pred, T1, !A, !B, !C),
+    Pred(K0, V0, !A, !B, !C),
+    tree234.foldr3(Pred, T0, !A, !B, !C).
+tree234.foldr3(Pred, four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
+        !A, !B, !C) :-
+    tree234.foldr3(Pred, T3, !A, !B, !C),
+    Pred(K2, V2, !A, !B, !C),
+    tree234.foldr3(Pred, T2, !A, !B, !C),
+    Pred(K1, V1, !A, !B, !C),
+    tree234.foldr3(Pred, T1, !A, !B, !C),
+    Pred(K0, V0, !A, !B, !C),
+    tree234.foldr3(Pred, T0, !A, !B, !C).
+
+tree234.foldr4(_Pred, empty, !A, !B, !C, !D).
+tree234.foldr4(Pred, two(K, V, T0, T1), !A, !B, !C, !D) :-
+	tree234.foldr4(Pred, T1, !A, !B, !C, !D),
+	Pred(K, V, !A, !B, !C, !D),
+	tree234.foldr4(Pred, T0, !A, !B, !C, !D).
+tree234.foldr4(Pred, three(K0, V0, K1, V1, T0, T1, T2), !A, !B, !C, !D) :-
+	tree234.foldr4(Pred, T2, !A, !B, !C, !D),
+	Pred(K1, V1, !A, !B, !C, !D),
+	tree234.foldr4(Pred, T1, !A, !B, !C, !D),
+	Pred(K0, V0, !A, !B, !C, !D),
+	tree234.foldr4(Pred, T0, !A, !B, !C, !D).
+tree234.foldr4(Pred, four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
+		!A, !B, !C, !D) :-
+	tree234.foldr4(Pred, T3, !A, !B, !C, !D),
+	Pred(K2, V2, !A, !B, !C, !D),
+	tree234.foldr4(Pred, T2, !A, !B, !C, !D),
+	Pred(K1, V1, !A, !B, !C, !D),
+	tree234.foldr4(Pred, T1, !A, !B, !C, !D),
+	Pred(K0, V0, !A, !B, !C, !D),
+	tree234.foldr4(Pred, T0, !A, !B, !C, !D).
+
+%------------------------------------------------------------------------------%
+
 tree234.map_values(_Pred, empty, empty).
 tree234.map_values(Pred, Tree0, Tree) :-
     Tree0 = two(K0, V0, Left0, Right0),
@@ -2645,6 +2777,10 @@
     P = (pred(W::in, X::in, Y::in, Z::out) is det :- Z = F(W, X, Y) ),
     tree234.foldl(P, T, A, B).
 
+tree234.foldr(F, T, A) = B :-
+    P = (pred(W::in, X::in, Y::in, Z::out) is det :- Z = F(W, X, Y) ),
+    tree234.foldr(P, T, A, B).
+
 tree234.map_values(F, T1) = T2 :-
     P = (pred(X::in, Y::in, Z::out) is det :- Z = F(X, Y) ),
     tree234.map_values(P, T1, T2).
Index: tests/hard_coded/Mmakefile
===================================================================
RCS file: /home/mercury1/repository/tests/hard_coded/Mmakefile,v
retrieving revision 1.325
diff -u -r1.325 Mmakefile
--- tests/hard_coded/Mmakefile	25 Jun 2007 00:58:14 -0000	1.325
+++ tests/hard_coded/Mmakefile	13 Jul 2007 03:44:16 -0000
@@ -128,6 +128,7 @@
 	list_series_int \
 	loop_inv_test \
 	loop_inv_test1 \
+	map_fold \
 	mapped_module \
 	merge_and_remove_dups \
 	minint_bug \
Index: tests/hard_coded/map_fold.exp
===================================================================
RCS file: tests/hard_coded/map_fold.exp
diff -N tests/hard_coded/map_fold.exp
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ tests/hard_coded/map_fold.exp	13 Jul 2007 03:44:21 -0000
@@ -0,0 +1,2 @@
+[10, 10, 9, 9, 8, 8, 7, 7, 6, 6, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1]
+[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10]
Index: tests/hard_coded/map_fold.m
===================================================================
RCS file: tests/hard_coded/map_fold.m
diff -N tests/hard_coded/map_fold.m
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ tests/hard_coded/map_fold.m	13 Jul 2007 03:03:58 -0000
@@ -0,0 +1,38 @@
+%-----------------------------------------------------------------------------%
+% map_fold.m
+% Ralph Becket <rafe at csse.unimelb.edu.au>
+% Fri Jul 13 12:50:24 EST 2007
+% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
+%
+% Test map.fold[lr].
+%
+%-----------------------------------------------------------------------------%
+
+:- module map_fold.
+
+:- interface.
+
+:- import_module io.
+
+
+
+:- pred main(io::di, io::uo) is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module int, list, map.
+
+%-----------------------------------------------------------------------------%
+
+main(!IO) :-
+    Map = list.foldl(func(I, M) = M ^ elem(I) := I, 1..10, map.init),
+    L = map.foldl(func(K, V, Xs) = [K, V | Xs], Map, []),
+    R = map.foldr(func(K, V, Xs) = [K, V | Xs], Map, []),
+    io.print(L, !IO), io.nl(!IO),
+    io.print(R, !IO), io.nl(!IO).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at csse.unimelb.edu.au
Administrative Queries: owner-mercury-developers at csse.unimelb.edu.au
Subscriptions:          mercury-developers-request at csse.unimelb.edu.au
--------------------------------------------------------------------------