Index: stdlib/map.ml
===================================================================
RCS file: /caml/ocaml/stdlib/map.ml,v
retrieving revision 1.17
diff -u -r1.17 map.ml
--- stdlib/map.ml	13 Aug 2005 20:59:37 -0000	1.17
+++ stdlib/map.ml	6 Oct 2007 10:18:15 -0000
@@ -35,6 +35,12 @@
     val fold: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
     val compare: ('a -> 'a -> int) -> 'a t -> 'a t -> int
     val equal: ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
+    val min_key : 'a t -> key
+    val max_key : 'a t -> key
+    val choose_key : 'a t -> key
+    val choose : 'a t -> 'a
+    val length : 'a t -> int
+    val pairs : 'a t -> (key * 'a) list
   end
 
 module Make(Ord: OrderedType) = struct
@@ -195,4 +201,25 @@
             equal_aux (cons_enum r1 e1) (cons_enum r2 e2)
       in equal_aux (cons_enum m1 End) (cons_enum m2 End)
 
+    let rec min_key = function
+        Empty -> raise Not_found
+      | Node(Empty, k, _, _, _) -> k
+      | Node(l, _, _, _, _) -> min_key l
+
+    let rec max_key = function
+        Empty -> raise Not_found
+      | Node(_, k, _, Empty, _) -> k
+      | Node(_, _, _, r, _) -> max_key r
+
+    let choose_key = function
+        Empty -> raise Not_found
+      | Node(_,k,_,_,_) -> k
+
+    let choose data = find (choose_key data) data
+
+    let rec length = function
+        Empty -> 0
+      | Node(l, _, _, r, _) -> (length l) + (length r) + 1
+
+    let pairs data = fold (fun k v l -> (k, v) :: l) data []
 end
Index: stdlib/map.mli
===================================================================
RCS file: /caml/ocaml/stdlib/map.mli,v
retrieving revision 1.33
diff -u -r1.33 map.mli
--- stdlib/map.mli	25 Oct 2005 18:34:07 -0000	1.33
+++ stdlib/map.mli	6 Oct 2007 10:18:15 -0000
@@ -103,6 +103,26 @@
        equal data.  [cmp] is the equality predicate used to compare
        the data associated with the keys. *)
 
+    val min_key : 'a t -> key
+    (** [min_key m] returns the smallest key in the map [m], or raises
+       [Not_found] if [m] is empty. *)
+
+    val max_key : 'a t -> key
+    (** [min_key m] returns the largest key in the map [m], or raises
+       [Not_found] if [m] is empty. *)
+
+    val choose_key : 'a t -> key
+    (** [choose_key m] returns an arbitrary key from the map [m] in O(1) time. *)
+
+    val choose : 'a t -> 'a
+    (** [choose m] returns an arbitrary element from the map [m] in O(1) time. *)
+
+    val length : 'a t -> int
+    (** [length m] returns the number of entries in [m] *)
+
+    val pairs : 'a t -> (key * 'a) list
+    (** [pairs m] returns a list of (key, value) pairs from the map [m], in some
+       unspecified order. *)
   end
 (** Output signature of the functor {!Map.Make}. *)
 
Index: stdlib/moreLabels.mli
===================================================================
RCS file: /caml/ocaml/stdlib/moreLabels.mli,v
retrieving revision 1.12
diff -u -r1.12 moreLabels.mli
--- stdlib/moreLabels.mli	23 Apr 2004 10:01:34 -0000	1.12
+++ stdlib/moreLabels.mli	6 Oct 2007 10:18:15 -0000
@@ -85,6 +85,12 @@
           'a t -> init:'b -> 'b
       val compare: cmp:('a -> 'a -> int) -> 'a t -> 'a t -> int
       val equal: cmp:('a -> 'a -> bool) -> 'a t -> 'a t -> bool
+      val min_key : 'a t -> key
+      val max_key : 'a t -> key
+      val choose_key : 'a t -> key
+      val choose : 'a t -> 'a
+      val length : 'a t -> int
+      val pairs : 'a t -> (key * 'a) list
   end
   module Make : functor (Ord : OrderedType) -> S with type key = Ord.t
 end