[m-dev.] For review: updates to library/rbtree.m

[Warwick Harvey]

Fergus wrote:
> On 12-May-2000, Warwick Harvey <wh at icparc.ic.ac.uk> wrote: 
> > As per some private mail exchanged with Fergus, I've been looking at the 
> > rbtree module, as an alternative to tree234 as the underlying 
> > implementation of map. It was missing a few things that tree234 has, 
> > and as such was not plug-in compatible. These changes fix that by 
> > bringing rbtree "up to speed", so to speak. 
> 
> That change looks good, Warwick.

Unfortunately, it didn't boot check (I should have verified that the
version I checked out worked first, so I'd know whether the problem was
with the rbtree module or not...  Doing that now).  Obviously I'll post
any patches needed to fix rbtree before I commit anything.

> I'd prefer the version with unique modes. 

Yup, my only concern with that was the code duplication, but, as
happens, lying in bed that night I figured out how to avoid it.  :-) 
Here's a diff between the old unique modes version and the new one, as
well as a full diff relative to the repository.

Probably some of the ( -> ; -> ; ) constructs in this module should be
converted to switches.  Perhaps `yes' and `no' insts could be added to
bool.m as well --- though maybe they wouldn't be used often enough to
warrant it (I couldn't find any other references to `bound(yes)' or
`bound(no)' in the compiler).

Cheers,
Warwick
-------------- next part --------------
--- rbtree.m.unique	Mon May 15 11:29:06 2000
+++ rbtree.m	Mon May 15 12:38:18 2000
@@ -170,7 +170,7 @@
 
 :- implementation.
 
-:- import_module int, require, std_util.
+:- import_module bool, int, require, std_util.
 
 
 :- type rbtree(K,V)	 --->	empty
@@ -750,72 +750,17 @@
 
 %-----------------------------------------------------------------------------%
 
-rbtree__delete(empty, _K, empty).
-rbtree__delete(red(K0, V0, L, R), K, Tree) :-
-	compare(Result, K, K0),
-	(	
-		Result = (=)
-	->
-		(
-			rbtree__remove_largest(L, NewK, NewV, NewL)
-		->
-			Tree = red(NewK, NewV, NewL, R)
-		;
-			% L must be empty
-			(
-				rbtree__remove_smallest(R, NewK, NewV, NewR)
-			->
-				Tree = red(NewK, NewV, empty, NewR)
-			;
-				% R must be empty
-				Tree = empty
-			)
-		)
-	;
-
-		Result = (<)
-	->
-		rbtree__delete(L, K, NewL),
-		Tree = red(K0, V0, NewL, R)
-	;
-		rbtree__delete(R, K, NewR),
-		Tree = red(K0, V0, L, NewR)
-	).
-rbtree__delete(black(K0, V0, L, R), K, Tree) :-
-	compare(Result, K, K0),
-	(	
-		Result = (=)
-	->
-		(
-			rbtree__remove_largest(L, NewK, NewV, NewL)
-		->
-			Tree = black(NewK, NewV, NewL, R)
-		;
-			% L must be empty
-			(
-				rbtree__remove_smallest(R, NewK, NewV, NewR)
-			->
-				Tree = black(NewK, NewV, empty, NewR)
-			;
-				% R must be empty
-				Tree = empty
-			)
-		)
-	;
-
-		Result = (<)
-	->
-		rbtree__delete(L, K, NewL),
-		Tree = black(K0, V0, NewL, R)
-	;
-		rbtree__delete(R, K, NewR),
-		Tree = black(K0, V0, L, NewR)
-	).
-
-%-----------------------------------------------------------------------------%
+rbtree__delete(Tree0, K, Tree) :-
+	rbtree__delete_2(Tree0, K, no, _, Tree).
 
-% rbtree_remove:
-%	Search down the tree, looking for the node to remove.  O(log N)
+% rbtree__delete_2(Tree0, Key, MustRemove, MaybeValue, Tree):
+%	Search the tree Tree0, looking for a node with key Key to delete.
+%	If MustRemove is `yes' and we don't find the key, fail.
+%	If we find the key, return it in MaybeValue and delete the node.
+%	Tree is the resulting tree, whether a node was removed or not.
+%
+% Deletion algorithm:
+%	Search down the tree, looking for the node to delete.  O(log N)
 %	When we find it, there are 4 possible conditions ->
 %		* Leaf node
 %		    Remove node  O(1)
@@ -823,14 +768,19 @@
 %		    Move maximum key of Left subtree to current node. O(log N)
 %		* Right subtree of node to be deleted exists
 %		    Move minimum key of Right subtree to current node. O(log N)
-%		* Both of node to be deleted left and right subtree exist
+%		* Both left and right subtrees of node to be deleted exist
 %		    Move maximum key of Left subtree to current node. O(log N)
 %
 %	Algorithm O(log N).
 
-rbtree__remove(empty, _K, _V, _Tree) :-
-	fail.
-rbtree__remove(red(K0, V0, L, R), K, V, Tree) :-
+:- pred rbtree__delete_2(rbtree(K, V), K, bool, maybe(V), rbtree(K, V)).
+:- mode rbtree__delete_2(di, in, in, uo, uo) is semidet.
+:- mode rbtree__delete_2(di, in, in(bound(no)), uo, uo) is det.
+:- mode rbtree__delete_2(in, in, in, out, out) is semidet.
+:- mode rbtree__delete_2(in, in, in(bound(no)), out, out) is det.
+
+rbtree__delete_2(empty, _K, no, no, empty).
+rbtree__delete_2(red(K0, V0, L, R), K, MustRemove, MaybeV, Tree) :-
 	compare(Result, K, K0),
 	(	
 		Result = (=)
@@ -850,18 +800,18 @@
 				Tree = empty
 			)
 		),
-		V = V0
+		MaybeV = yes(V0)
 	;
 
 		Result = (<)
 	->
-		rbtree__remove(L, K, V, NewL),
+		rbtree__delete_2(L, K, MustRemove, MaybeV, NewL),
 		Tree = red(K0, V0, NewL, R)
 	;
-		rbtree__remove(R, K, V, NewR),
+		rbtree__delete_2(R, K, MustRemove, MaybeV, NewR),
 		Tree = red(K0, V0, L, NewR)
 	).
-rbtree__remove(black(K0, V0, L, R), K, V, Tree) :-
+rbtree__delete_2(black(K0, V0, L, R), K, MustRemove, MaybeV, Tree) :-
 	compare(Result, K, K0),
 	(	
 		Result = (=)
@@ -881,17 +831,22 @@
 				Tree = empty
 			)
 		),
-		V = V0
+		MaybeV = yes(V0)
 	;
 
 		Result = (<)
 	->
-		rbtree__remove(L, K, V, NewL),
+		rbtree__delete_2(L, K, MustRemove, MaybeV, NewL),
 		Tree = black(K0, V0, NewL, R)
 	;
-		rbtree__remove(R, K, V, NewR),
+		rbtree__delete_2(R, K, MustRemove, MaybeV, NewR),
 		Tree = black(K0, V0, L, NewR)
 	).
+
+%-----------------------------------------------------------------------------%
+
+rbtree__remove(Tree0, K, V, Tree) :-
+	rbtree__delete_2(Tree0, K, yes, yes(V), Tree).
 
 rbtree__remove(Tree0, K, Tree) :-
 	rbtree__remove(Tree0, K, _, Tree).
-------------- next part --------------
Index: rbtree.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/rbtree.m,v
retrieving revision 1.12
diff -u -r1.12 rbtree.m
--- rbtree.m	2000/05/12 17:28:44	1.12
+++ rbtree.m	2000/05/15 11:40:08
@@ -44,8 +44,12 @@
 
 	% Initialise the data structure.
 :- pred rbtree__init(rbtree(K, V)).
-:- mode rbtree__init(out) is det.
+:- mode rbtree__init(uo) is det.
 
+	% Check whether a tree is empty.
+:- pred rbtree__is_empty(rbtree(K, V)).
+:- mode rbtree__is_empty(in) is semidet.
+
 	% Inserts a new key-value pair into the tree.  Fails if key 
 	% already in the tree.
 :- pred rbtree__insert(rbtree(K, V), K, V, rbtree(K, V)).
@@ -59,12 +63,16 @@
 	% Sets a value irregardless of whether key exists or not.  Never
 	% fails.
 :- pred rbtree__set(rbtree(K, V), K, V, rbtree(K, V)).
+:- mode rbtree__set(di, di, di, uo) is det.
 :- mode rbtree__set(in, in, in, out) is det.
 
 	% Insert a duplicate key into the tree.  Never fails.
 :- pred rbtree__insert_duplicate(rbtree(K, V), K, V, rbtree(K, V)).
 :- mode rbtree__insert_duplicate(in, in, in, out) is det.
 
+:- pred rbtree__member(rbtree(K, V), K, V).
+:- mode rbtree__member(in, out, out) is nondet.
+
 	% Search for a key-value pair using the key.  Fails if key doesn't
 	% exist.
 :- pred rbtree__search(rbtree(K, V), K, V).
@@ -102,13 +110,33 @@
 	% Delete the key value pair associated with a key.  Does nothing
 	% if the key doesn't exist.
 :- pred rbtree__delete(rbtree(K, V), K, rbtree(K, V)).
+:- mode rbtree__delete(di, in, uo) is det.
 :- mode rbtree__delete(in, in, out) is det.
 
 	% Remove the key value pair associated with a key.  Fails
 	% if the key doesn't exist.
+:- pred rbtree__remove(rbtree(K, V), K, V, rbtree(K, V)).
+:- mode rbtree__remove(di, in, uo, uo) is semidet.
+:- mode rbtree__remove(in, in, out, out) is semidet.
+
+	% Same as above, except this version does not return the value
+	% corresponding to the key.  Its use is deprecated, but it is
+	% kept for compatibility with older versions of this library.
 :- pred rbtree__remove(rbtree(K, V), K, rbtree(K, V)).
 :- mode rbtree__remove(in, in, out) is semidet.
 
+	% Deletes the node with the minimum K from the tree, and returns
+	% the key and value fields.
+:- pred rbtree__remove_smallest(rbtree(K, V), K, V, rbtree(K, V)).
+:- mode rbtree__remove_smallest(di, uo, uo, uo) is semidet.
+:- mode rbtree__remove_smallest(in, out, out, out) is semidet.
+
+	% Deletes the node with the maximum K from the tree, and returns
+	% the key and value fields.
+:- pred rbtree__remove_largest(rbtree(K, V), K, V, rbtree(K, V)).
+:- mode rbtree__remove_largest(di, uo, uo, uo) is semidet.
+:- mode rbtree__remove_largest(in, out, out, out) is semidet.
+
 	% Returns an in-order list of all the keys in the rbtree.
 :- pred rbtree__keys(rbtree(K, V), list(K)).
 :- mode rbtree__keys(in, out) is det.
@@ -128,11 +156,21 @@
 :- pred rbtree__rbtree_to_assoc_list(rbtree(K, V), assoc_list(K, V)).
 :- mode rbtree__rbtree_to_assoc_list(in, out) is det.
 
+:- pred rbtree__foldl(pred(K, V, T, T), rbtree(K, V), T, T).
+:- mode rbtree__foldl(pred(in, in, in, out) is det, in, in, out) is det.
+:- mode rbtree__foldl(pred(in, in, in, out) is semidet, in, in, out)
+		is semidet.
+:- mode rbtree__foldl(pred(in, in, di, uo) is det, in, di, uo) is det.
+
+:- pred rbtree__map_values(pred(K, V, W), rbtree(K, V), rbtree(K, W)).
+:- mode rbtree__map_values(pred(in, in, out) is det, in, out) is det.
+:- mode rbtree__map_values(pred(in, in, out) is semidet, in, out) is semidet.
+
 %-----------------------------------------------------------------------------%
 
 :- implementation.
 
-:- import_module int, require, std_util.
+:- import_module bool, int, require, std_util.
 
 
 :- type rbtree(K,V)	 --->	empty
@@ -143,6 +181,9 @@
 
 rbtree__init(empty).
 
+rbtree__is_empty(Tree) :-
+	Tree = empty.
+
 %-----------------------------------------------------------------------------%
 
 % Special conditions that must be satisfied by Red-Black trees.
@@ -328,6 +369,7 @@
 
 
 :- pred rbtree__set_2(rbtree(K, V), K, V, rbtree(K, V)). 
+:- mode rbtree__set_2(di, di, di, uo) is det.
 :- mode rbtree__set_2(in, in, in, out) is det.
 
 % rbtree__set_2:
@@ -395,7 +437,10 @@
 					TreeR = red(K0, V0, LRR, R0),
 					Tree = black(LRK, LRV, TreeL, TreeR)
 				;
-					Tree = black(K0, V0, NewL, R0)
+					% NewL2 == NewL, but this hack 
+					% needed for unique modes to work.
+					NewL2 = red(LK, LV, LL, LR),
+					Tree = black(K0, V0, NewL2, R0)
 				)
 			;
 				Tree = black(K0, V0, NewL, R0)
@@ -422,7 +467,10 @@
 					TreeL = red(K0, V0, L0, RL),
 					Tree = black(RK, RV, TreeL, RR)
 				;
-					Tree = black(K0, V0, L0, NewR)
+					% NewR2 == NewR, but this hack 
+					% needed for unique modes to work.
+					NewR2 = red(RK, RV, RL, RR),
+					Tree = black(K0, V0, L0, NewR2)
 				)
 			;
 				Tree = black(K0, V0, L0, NewR)
@@ -584,6 +632,28 @@
 
 %-----------------------------------------------------------------------------%
 
+rbtree__member(empty, _K, _V) :- fail.
+rbtree__member(red(K0, V0, Left, Right), K, V) :-
+	(
+		K = K0,
+		V = V0
+	;
+		rbtree__member(Left, K, V)
+	;
+		rbtree__member(Right, K, V)
+	).
+rbtree__member(black(K0, V0, Left, Right), K, V) :-
+	(
+		K = K0,
+		V = V0
+	;
+		rbtree__member(Left, K, V)
+	;
+		rbtree__member(Right, K, V)
+	).
+
+%-----------------------------------------------------------------------------%
+
 rbtree__search(Tree, K, V) :-
 	( Tree = red(K0, V0, Left, Right)
 	; Tree = black(K0, V0, Left, Right)
@@ -681,18 +751,16 @@
 %-----------------------------------------------------------------------------%
 
 rbtree__delete(Tree0, K, Tree) :-
-	(
-		rbtree__remove(Tree0, K, Tree1)
-	->
-		Tree = Tree1
-	;
-		Tree = Tree0
-	).
-	
-%-----------------------------------------------------------------------------%
+	rbtree__delete_2(Tree0, K, no, _, Tree).
 
-% rbtree_remove:
-%	Search down the tree, looking for the node to remove.  O(log N)
+% rbtree__delete_2(Tree0, Key, MustRemove, MaybeValue, Tree):
+%	Search the tree Tree0, looking for a node with key Key to delete.
+%	If MustRemove is `yes' and we don't find the key, fail.
+%	If we find the key, return it in MaybeValue and delete the node.
+%	Tree is the resulting tree, whether a node was removed or not.
+%
+% Deletion algorithm:
+%	Search down the tree, looking for the node to delete.  O(log N)
 %	When we find it, there are 4 possible conditions ->
 %		* Leaf node
 %		    Remove node  O(1)
@@ -700,84 +768,96 @@
 %		    Move maximum key of Left subtree to current node. O(log N)
 %		* Right subtree of node to be deleted exists
 %		    Move minimum key of Right subtree to current node. O(log N)
-%		* Both of node to be deleted left and right subtree exist
+%		* Both left and right subtrees of node to be deleted exist
 %		    Move maximum key of Left subtree to current node. O(log N)
 %
 %	Algorithm O(log N).
 
-rbtree__remove(empty, _K, _Tree) :-
-	fail.
-rbtree__remove(red(K0, V0, L, R), K, Tree) :-
+:- pred rbtree__delete_2(rbtree(K, V), K, bool, maybe(V), rbtree(K, V)).
+:- mode rbtree__delete_2(di, in, in, uo, uo) is semidet.
+:- mode rbtree__delete_2(di, in, in(bound(no)), uo, uo) is det.
+:- mode rbtree__delete_2(in, in, in, out, out) is semidet.
+:- mode rbtree__delete_2(in, in, in(bound(no)), out, out) is det.
+
+rbtree__delete_2(empty, _K, no, no, empty).
+rbtree__delete_2(red(K0, V0, L, R), K, MustRemove, MaybeV, Tree) :-
 	compare(Result, K, K0),
 	(	
 		Result = (=)
 	->
 		(
-			L = empty
-		->	
+			rbtree__remove_largest(L, NewK, NewV, NewL)
+		->
+			Tree = red(NewK, NewV, NewL, R)
+		;
+			% L must be empty
 			(
-				R = empty
+				rbtree__remove_smallest(R, NewK, NewV, NewR)
 			->
-				Tree = empty
+				Tree = red(NewK, NewV, empty, NewR)
 			;
-				rbtree__get_tree_min(R, NewK, NewV, NewR),
-				Tree = red(NewK, NewV, L, NewR)
+				% R must be empty
+				Tree = empty
 			)
-		;
-			rbtree__get_tree_max(L, NewK, NewV, NewL),
-			Tree = red(NewK, NewV, NewL, R)
-		)
+		),
+		MaybeV = yes(V0)
 	;
 
 		Result = (<)
 	->
-		rbtree__remove(L, K, NewL),
+		rbtree__delete_2(L, K, MustRemove, MaybeV, NewL),
 		Tree = red(K0, V0, NewL, R)
 	;
-		rbtree__remove(R, K, NewR),
+		rbtree__delete_2(R, K, MustRemove, MaybeV, NewR),
 		Tree = red(K0, V0, L, NewR)
 	).
-rbtree__remove(black(K0, V0, L, R), K, Tree) :-
+rbtree__delete_2(black(K0, V0, L, R), K, MustRemove, MaybeV, Tree) :-
 	compare(Result, K, K0),
 	(	
 		Result = (=)
 	->
 		(
-			L = empty
-		->	
+			rbtree__remove_largest(L, NewK, NewV, NewL)
+		->
+			Tree = black(NewK, NewV, NewL, R)
+		;
+			% L must be empty
 			(
-				R = empty
+				rbtree__remove_smallest(R, NewK, NewV, NewR)
 			->
-				Tree = empty
+				Tree = black(NewK, NewV, empty, NewR)
 			;
-				rbtree__get_tree_min(R, NewK, NewV, NewR),
-				Tree = black(NewK, NewV, L, NewR)
+				% R must be empty
+				Tree = empty
 			)
-		;
-			rbtree__get_tree_max(L, NewK, NewV, NewL),
-			Tree = black(NewK, NewV, NewL, R)
-		)
+		),
+		MaybeV = yes(V0)
 	;
 
 		Result = (<)
 	->
-		rbtree__remove(L, K, NewL),
+		rbtree__delete_2(L, K, MustRemove, MaybeV, NewL),
 		Tree = black(K0, V0, NewL, R)
 	;
-		rbtree__remove(R, K, NewR),
+		rbtree__delete_2(R, K, MustRemove, MaybeV, NewR),
 		Tree = black(K0, V0, L, NewR)
 	).
 
-% rbtree__get_tree_max:
+%-----------------------------------------------------------------------------%
+
+rbtree__remove(Tree0, K, V, Tree) :-
+	rbtree__delete_2(Tree0, K, yes, yes(V), Tree).
+
+rbtree__remove(Tree0, K, Tree) :-
+	rbtree__remove(Tree0, K, _, Tree).
+
+% rbtree__remove_largest:
 %	Deletes the node with the maximum K from the tree, and returns the
 %	key and value fields.
 
-:- pred rbtree__get_tree_max(rbtree(K, V), K, V, rbtree(K, V)).
-:- mode rbtree__get_tree_max(in, out, out, out) is det.
-
-rbtree__get_tree_max(empty, _K, _V, _Tree) :-
-	error("rbtree__get_tree_max: attempted to get K+V from empty tree").
-rbtree__get_tree_max(red(K0, V0, L, R), NewK, NewV, Tree) :-
+rbtree__remove_largest(empty, _K, _V, _Tree) :-
+	fail.
+rbtree__remove_largest(red(K0, V0, L, R), NewK, NewV, Tree) :-
 	(
 		R = empty
 	->
@@ -785,10 +865,10 @@
 		NewV = V0,
 		Tree = L
 	;
-		rbtree__get_tree_max(R, NewK, NewV, NewR),
+		rbtree__remove_largest(R, NewK, NewV, NewR),
 		Tree = red(K0, V0, L, NewR)
 	).
-rbtree__get_tree_max(black(K0, V0, L, R), NewK, NewV, Tree) :-
+rbtree__remove_largest(black(K0, V0, L, R), NewK, NewV, Tree) :-
 	(
 		R = empty
 	->
@@ -796,20 +876,17 @@
 		NewV = V0,
 		Tree = L
 	;
-		rbtree__get_tree_max(R, NewK, NewV, NewR),
+		rbtree__remove_largest(R, NewK, NewV, NewR),
 		Tree = black(K0, V0, L, NewR)
 	).
 
-% rbtree__get_tree_min:
+% rbtree__remove_smallest:
 %	Deletes the node with the minimum K from the tree, and returns the
 %	key and value fields.
 
-:- pred rbtree__get_tree_min(rbtree(K, V), K, V, rbtree(K, V)).
-:- mode rbtree__get_tree_min(in, out, out, out) is det.
-
-rbtree__get_tree_min(empty, _K, _V, _Tree) :-
-	error("rbtree__get_tree_min: attempted to get K+V from empty tree").
-rbtree__get_tree_min(red(K0, V0, L, R), NewK, NewV, Tree) :-
+rbtree__remove_smallest(empty, _K, _V, _Tree) :-
+	fail.
+rbtree__remove_smallest(red(K0, V0, L, R), NewK, NewV, Tree) :-
 	(
 		L = empty
 	->
@@ -817,10 +894,10 @@
 		NewV = V0,
 		Tree = R
 	;
-		rbtree__get_tree_min(L, NewK, NewV, NewL),
+		rbtree__remove_smallest(L, NewK, NewV, NewL),
 		Tree = red(K0, V0, NewL, R)
 	).
-rbtree__get_tree_min(black(K0, V0, L, R), NewK, NewV, Tree) :-
+rbtree__remove_smallest(black(K0, V0, L, R), NewK, NewV, Tree) :-
 	(
 		L = empty
 	->
@@ -828,7 +905,7 @@
 		NewV = V0,
 		Tree = R
 	;
-		rbtree__get_tree_min(L, NewK, NewV, NewL),
+		rbtree__remove_smallest(L, NewK, NewV, NewL),
 		Tree = black(K0, V0, NewL, R)
 	).
 
@@ -890,6 +967,34 @@
 	list__append(L0, [K0 - V0|L1], L).
 
 %-----------------------------------------------------------------------------%
+
+rbtree__foldl(_Pred, empty, Acc, Acc).
+rbtree__foldl(Pred, red(K, V, Left, Right), Acc0, Acc) :-
+	rbtree__foldl(Pred, Left, Acc0, Acc1),
+	call(Pred, K, V, Acc1, Acc2),
+	rbtree__foldl(Pred, Right, Acc2, Acc).
+rbtree__foldl(Pred, black(K, V, Left, Right), Acc0, Acc) :-
+	rbtree__foldl(Pred, Left, Acc0, Acc1),
+	call(Pred, K, V, Acc1, Acc2),
+	rbtree__foldl(Pred, Right, Acc2, Acc).
+
+%-----------------------------------------------------------------------------%
+
+rbtree__map_values(_Pred, empty, empty).
+rbtree__map_values(Pred, Tree0, Tree) :-
+	Tree0 = red(K0, V0, Left0, Right0),
+	Tree  = red(K0, W0, Left, Right),
+	call(Pred, K0, V0, W0),
+	rbtree__map_values(Pred, Left0, Left),
+	rbtree__map_values(Pred, Right0, Right).
+rbtree__map_values(Pred, Tree0, Tree) :-
+	Tree0 = black(K0, V0, Left0, Right0),
+	Tree  = black(K0, W0, Left, Right),
+	call(Pred, K0, V0, W0),
+	rbtree__map_values(Pred, Left0, Left),
+	rbtree__map_values(Pred, Right0, Right).
+
+%-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 % Ralph Becket <rwab1 at cl.cam.ac.uk> 29/04/99
 % 	Function forms added.
@@ -916,6 +1021,10 @@
 
 :- func rbtree__rbtree_to_assoc_list(rbtree(K, V)) = assoc_list(K, V).
 
+:- func rbtree__foldl(func(K, V, T) = T, rbtree(K, V), T) = T.
+
+:- func rbtree__map_values(func(K, V) = W, rbtree(K, V)) = rbtree(K, W).
+
 % ---------------------------------------------------------------------------- %
 % ---------------------------------------------------------------------------- %
 
@@ -951,4 +1060,11 @@
 rbtree__rbtree_to_assoc_list(RBT) = AL :-
 	rbtree__rbtree_to_assoc_list(RBT, AL).
 
+rbtree__foldl(F, T, A) = B :-
+	P = ( pred(W::in, X::in, Y::in, Z::out) is det :- Z = F(W, X, Y) ),
+	rbtree__foldl(P, T, A, B).
+
+rbtree__map_values(F, T1) = T2 :-
+	P = ( pred(X::in, Y::in, Z::out) is det :- Z = F(X, Y) ),
+	rbtree__map_values(P, T1, T2).