Patch submission: More Lists (1)

diff -urN ocaml-extlib-read-only.orig/extlib/extList.ml ocaml-extlib-read-only/extlib/extList.ml
--- ocaml-extlib-read-only.orig/extlib/extList.ml	2008-08-30 15:11:51.000000000 +0200
+++ ocaml-extlib-read-only/extlib/extList.ml	2008-08-30 15:47:33.000000000 +0200
@@ -3,6 +3,7 @@
  * Copyright (C) 2003 Brian Hurt
  * Copyright (C) 2003 Nicolas Cannasse
  * Copyright (C) 2008 Red Hat Inc.
+ * Copyright (C) 2008 David Teller
  * 
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
@@ -38,6 +39,12 @@
 
 let dummy_node () = { hd = Obj.magic (); tl = [] }
 
+let cons h t = h::t
+
+let is_empty = function
+  | [] -> true
+  | _  -> false
+
 let hd = function
 	| [] -> raise Empty_list
 	| h :: t -> h
@@ -55,6 +62,8 @@
 	in
 	loop index l
 
+let at = nth
+
 let append l1 l2 =
 	match l1 with
 	| [] -> l2
@@ -121,16 +130,28 @@
 	dummy.tl
 
 (* takewhile and dropwhile by Richard W.M. Jones. *)
-let rec takewhile f = function
+let rec take_while f = function
   | [] -> []
-  | x :: xs when f x -> x :: takewhile f xs
+  | x :: xs when f x -> x :: take_while f xs
   | _ -> []
 
-let rec dropwhile f = function
+let rec drop_while f = function
   | [] -> []
-  | x :: xs when f x -> dropwhile f xs
+  | x :: xs when f x -> drop_while f xs
   | xs -> xs
 
+let takewhile = take_while
+let dropwhile = drop_while
+
+let make_compare c l1 l2 =
+  let rec aux l1 l2 = match (l1, l2) with
+    | (h1::t1, h2::t2) -> let result = c h1 h2 in
+	if result = 0 then aux t1 t2
+	else               result
+    | ([],     []    ) -> 0
+    | (_,      []    ) -> 1
+    | ([],     _     ) -> -1
+  in aux l1 l2
 
 let rec unique ?(cmp = ( = )) l =
 	let rec loop dst = function
@@ -161,7 +182,7 @@
 	let dummy = dummy_node() in
 	loop dummy l;
 	dummy.tl
-
+	
 let rec find_map f = function
   | [] -> raise Not_found
   | x :: xs ->
@@ -171,6 +192,8 @@
 
 let fold_right_max = 1000
 
+let fold_right_max = 1000
+
 let fold_right f l init =
 	let rec tail_loop acc = function
 		| [] -> acc
@@ -304,6 +327,35 @@
 	in
 	loop 0 l
 
+let rec index_of e l =
+  let rec loop n = function
+    | []              -> None
+    | h::t when h = e -> Some n
+    | _::t            -> loop ( n + 1 ) t
+  in loop 0 l
+
+let rec index_ofq e l =
+  let rec loop n = function
+    | []               -> None
+    | h::t when h == e -> Some n
+    | _::t             -> loop ( n + 1 ) t
+  in loop 0 l
+
+let rec rindex_of e l =
+  let rec loop n acc = function
+    | []              -> acc
+    | h::t when h = e -> loop ( n + 1) ( Some n ) t
+    | _::t            -> loop ( n + 1 ) acc       t
+  in loop 0 None l
+
+let rec rindex_ofq e l =
+  let rec loop n acc = function
+    | []               -> acc
+    | h::t when h == e -> loop ( n + 1) ( Some n ) t
+    | _::t             -> loop ( n + 1 ) acc       t
+  in loop 0 None l
+
+
 let filter = find_all
 
 let partition p lst = 
@@ -431,7 +483,9 @@
 			let r = { hd = h; tl = [] } in
 			inj r, loop (index-1) r t
 
-let find_exc f e l =
+let split_at = split_nth
+
+let find_exn f e l =
 	try
 		find f l
 	with
@@ -511,6 +565,50 @@
 		r) h e in
 	h.tl
 
+let backwards l = enum (rev l)
+
+let of_backwards e =
+  let rec aux acc = match Enum.get e with
+    | Some h -> aux (h::acc)
+    | None   -> acc
+  in aux []
+
+let assoc_inv e l =
+  let rec aux = function
+  | []                  -> raise Not_found
+  | (a,b)::t when b = e -> a
+  | _::t                -> aux t
+  in aux l
+
+
+  let rfind p l =
+    try  Some (rfind p l)
+    with Not_found -> None
+
+  let findi p l =
+    try  Some (findi p l)
+    with Not_found -> None
+      
+  let split_at n l =
+    try   `Ok (split_at n l)
+    with  Invalid_index i -> `Invalid_index i
+
+  let at n l =
+    try `Ok (at n l)
+    with Invalid_index i -> `Invalid_index i
+
+  let assoc e l =
+    try Some (assoc e l)
+    with Not_found -> None
+
+  let assq e l =
+    try Some (assq e l)
+    with Not_found -> None
+
+  let assoc_inv e l =
+    try Some (assoc_inv e l)
+    with Not_found -> None
 end
 
+
 let ( @ ) = List.append
diff -urN ocaml-extlib-read-only.orig/extlib/extList.mli ocaml-extlib-read-only/extlib/extList.mli
--- ocaml-extlib-read-only.orig/extlib/extList.mli	2008-08-30 15:11:51.000000000 +0200
+++ ocaml-extlib-read-only/extlib/extList.mli	2008-08-30 15:47:36.000000000 +0200
@@ -2,6 +2,8 @@
  * ExtList - additional and modified functions for lists.
  * Copyright (C) 2003 Brian Hurt
  * Copyright (C) 2003 Nicolas Cannasse
+ * Copyright (C) 2008 Red Hat Inc.
+ * Copyright (C) 2008 David Teller
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
@@ -21,61 +23,218 @@
 
 (** Additional and modified functions for lists.
 
-	The OCaml standard library provides a module for list functions.
-	This ExtList module can be used to override the List module or
-	as a standalone module. It provides new functions and modify
-	the behavior of some other ones (in particular all functions
-	are now {b tail-recursive}).
+    The OCaml standard library provides a module for list functions.
+    This ExtList module can be used to override the List module or
+    as a standalone module. It provides new functions and modify
+    the behavior of some other ones (in particular all functions
+    are now {b tail-recursive}).
+
+    The following functions have the same behavior as the [List]
+    module ones but are tail-recursive: [map], [append], [concat],
+    [flatten], [fold_right], [remove_assoc], [remove_assq],
+    [split]. That means they will not
+    cause a [Stack_overflow] when used on very long list.
+
+    The implementation might be a little more slow in bytecode,
+    but compiling in native code will not affect performances. 
 *)
 
 module List :
     sig
 
-	(** {6 New functions} *)
+      (** List operations.  *)
+
+
+      (**{6 Base operations}*)
+	val length : 'a list -> int
+	  (** Return the length (number of elements) of the given list. *)
+
+	val hd : 'a list -> 'a
+	(** Returns the first element of the list or raise [Empty_list] if the
+	 list is empty. *)
+
+	val tl : 'a list -> 'a list
+	(** Returns the list without its first elements or raise [Empty_list] if
+	 the list is empty. *)
+
+	val is_empty : 'a list -> bool
+	  (** [is_empty e] returns true if [e] does not contains any element. *)
+
+	val cons : 'a -> 'a list -> 'a list
+	  (** [cons h t] returns the list starting with [h] and continuing as [t] *)
+
+	val first : 'a list -> 'a
+	  (** Returns the first element of the list, or raise [Empty_list] if
+	      the list is empty (similar to [hd]). *)
+
+	val last : 'a list -> 'a
+	  (** Returns the last element of the list, or raise [Empty_list] if
+	      the list is empty. This function takes linear time. *)
+
+	val at : 'a list -> int -> 'a
+	  (** [at l n] returns the n-th element of the list [l] or raise
+	      [Invalid_index] is the index is outside of [l] bounds. *)
+
+	val rev : 'a list -> 'a list
+	  (** List reversal. *)
+
+	val append : 'a list -> 'a list -> 'a list
+	  (** Catenate two lists.  Same function as the infix operator [@].
+	      Tail-recursive (length of the first argument).*)
+
+	val rev_append : 'a list -> 'a list -> 'a list
+	  (** [List.rev_append l1 l2] reverses [l1] and concatenates it to [l2].
+	      This is equivalent to {!List.rev}[ l1 @ l2], but [rev_append] is
+	      more efficient. *)
+
+	val concat : 'a list list -> 'a list
+	  (** Concatenate a list of lists.  The elements of the argument are all
+	      concatenated together (in the same order) to give the result.
+	      Tail-recursive
+	      (length of the argument + length of the longest sub-list). *)
+
+	val flatten : 'a list list -> 'a list
+	  (** Same as [concat]. *)
+
+	(**{6 Constructors}*)
+	  
+	val make : int -> 'a -> 'a list
+	  (** Similar to [String.make], [make n x] returns a
+	      list containing [n] elements [x]. *)
 
 	val init : int -> (int -> 'a) -> 'a list
 	(** Similar to [Array.init], [init n f] returns the list containing
 	 the results of (f 0),(f 1).... (f (n-1)).
 	 Raise [Invalid_arg "ExtList.init"] if n < 0.*)
 
-	val make : int -> 'a -> 'a list
-	  (** Similar to [String.make], [make n x] returns a
-	    * list containing [n] elements [x].
-    	    *)
 
-	val first : 'a list -> 'a
-	(** Returns the first element of the list, or raise [Empty_list] if
-	 the list is empty (similar to [hd]). *)
-
-	val last : 'a list -> 'a
-	(** Returns the last element of the list, or raise [Empty_list] if
-	 the list is empty. This function takes linear time. *)
+	(**{6 Iterators}*)
+	val iter : ('a -> unit) -> 'a list -> unit
+	  (** [List.iter f [a1; ...; an]] applies function [f] in turn to
+	      [a1; ...; an]. It is equivalent to
+	      [begin f a1; f a2; ...; f an; () end]. *)
 
 	val iteri : (int -> 'a -> 'b) -> 'a list -> unit
 	(** [iteri f l] will call [(f 0 a0);(f 1 a1) ... (f n an)] where
 	 [a0..an] are the elements of the list [l]. *)
 
+	val map : ('a -> 'b) -> 'a list -> 'b list
+	  (** [map f [a1; ...; an]] applies function [f] to [a1, ..., an],
+	      and builds the list [[f a1; ...; f an]]
+	      with the results returned by [f].  Tail-recursive. *)
+
 	val mapi : (int -> 'a -> 'b) -> 'a list -> 'b list
 	(** [mapi f l] will build the list containing
 	 [(f 0 a0);(f 1 a1) ... (f n an)] where [a0..an] are the elements of
 	 the list [l]. *)
 
-	val rfind : ('a -> bool) -> 'a list -> 'a
-	(** [rfind p l] returns the last element [x] of [l] such as [p x] returns
-	 [true] or raises [Not_found] if such element as not been found. *)
 
-	val find_exc : ('a -> bool) -> exn -> 'a list -> 'a
-	(** [find_exc p e l] returns the first element of [l] such as [p x]
-	 returns [true] or raises [e] if such element as not been found. *)
+	val rev_map : ('a -> 'b) -> 'a list -> 'b list
+	  (** [List.rev_map f l] gives the same result as
+	      {!List.rev}[ (]{!List.map}[ f l)], but is
+	      more efficient. *)
+
+	val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
+	  (** [List.fold_left f a [b1; ...; bn]] is
+	      [f (... (f (f a b1) b2) ...) bn]. *)
+
+	val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
+	  (** [List.fold_right f [a1; ...; an] b] is
+	      [f a1 (f a2 (... (f an b) ...))].  Tail-recursive. *)
+
+
+
+	(** {6 Iterators on two lists} *)
+	val iter2 : ('a -> 'b -> unit) -> 'a list -> 'b list -> unit
+	  (** [List.iter2 f [a1; ...; an] [b1; ...; bn]] calls in turn
+	      [f a1 b1; ...; f an bn].
+	      Raise [Different_list_size] if the two lists have
+	      different lengths. *)
+
+	val map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
+	  (** [List.map2 f [a1; ...; an] [b1; ...; bn]] is
+	      [[f a1 b1; ...; f an bn]].
+	      Raise [Different_list_size] if the two lists have
+	      different lengths.  Tail-recursive. *)
+
+	val rev_map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
+	  (** [List.rev_map2 f l1 l2] gives the same result as
+	      {!List.rev}[ (]{!List.map2}[ f l1 l2)], but is tail-recursive and
+	      more efficient. *)
+
+	val fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b list -> 'c list -> 'a
+	  (** [List.fold_left2 f a [b1; ...; bn] [c1; ...; cn]] is
+	      [f (... (f (f a b1 c1) b2 c2) ...) bn cn].
+	      Raise [Different_list_size] if the two lists have
+	      different lengths. *)
+
+	val fold_right2 : ('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list -> 'c -> 'c
+	  (** [List.fold_right2 f [a1; ...; an] [b1; ...; bn] c] is
+	      [f a1 b1 (f a2 b2 (... (f an bn c) ...))].
+	      Raise [Different_list_size] if the two lists have
+	      different lengths.  Tail-recursive. *)
+
+	  (**{6 List scanning}*)
+	val for_all : ('a -> bool) -> 'a list -> bool
+	  (** [for_all p [a1; ...; an]] checks if all elements of the list
+	      satisfy the predicate [p]. That is, it returns
+	      [(p a1) && (p a2) && ... && (p an)]. *)
+
+	val exists : ('a -> bool) -> 'a list -> bool
+	  (** [exists p [a1; ...; an]] checks if at least one element of
+	      the list satisfies the predicate [p]. That is, it returns
+	      [(p a1) || (p a2) || ... || (p an)]. *)
+
+	val for_all2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
+	  (** Same as {!List.for_all}, but for a two-argument predicate.
+	      Raise [Invalid_argument] if the two lists have
+	      different lengths. *)
+
+	val exists2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
+	  (** Same as {!List.exists}, but for a two-argument predicate.
+	      Raise [Invalid_argument] if the two lists have
+	      different lengths. *)
+
+	val mem : 'a -> 'a list -> bool
+	  (** [mem a l] is true if and only if [a] is equal
+	      to an element of [l]. *)
+
+	val memq : 'a -> 'a list -> bool
+	  (** Same as {!List.mem}, but uses physical equality instead of structural
+	      equality to compare list elements. *)
+
+	(**{6 List searching}*)
+
+
+	val find : ('a -> bool) -> 'a list -> 'a
+	  (** [find p l] returns the first element of [l] such as [p x]
+	      returns [true] or raises [Not_found] if such an element
+	      has not been found.*)
+
+	val find_exn : ('a -> bool) -> exn -> 'a list -> 'a
+	(** [find_exn p e l] returns the first element of [l] such as [p x]
+	 returns [true] or raises [e] if such an element has not been found. *)
 
 	val findi : (int -> 'a -> bool) -> 'a list -> (int * 'a)
 	(** [findi p e l] returns the first element [ai] of [l] along with its
 	 index [i] such that [p i ai] is true, or raises [Not_found] if no
 	 such element has been found. *)
 
-	val unique : ?cmp:('a -> 'a -> bool) -> 'a list -> 'a list
-	(** [unique cmp l] returns the list [l] without any duplicate element.
-	 Default comparator ( = ) is used if no comparison function specified. *)
+	val find_map : ('a -> 'b option) -> 'a list -> 'b
+        (** [find_map pred list] finds the first element of [list] for which
+            [pred element] returns [Some r].  It returns [r] immediately
+            once found or raises [Not_found] if no element matches the
+            predicate.  See also {!filter_map}. *)
+
+
+	val rfind : ('a -> bool) -> 'a list -> 'a
+	(** [rfind p l] returns the last element [x] of [l] such as [p x] returns
+	 [true] or raises [Not_found] if such element as not been found. *)
+
+	val filter : ('a -> bool) -> 'a list -> 'a list
+	  (** [filter p l] returns all the elements of the list [l]
+	      that satisfy the predicate [p].  The order of the elements
+	      in the input list is preserved.  *)
 
 	val filter_map : ('a -> 'b option) -> 'a list -> 'b list
 	(** [filter_map f l] call [(f a0) (f a1).... (f an)] where [a0..an] are
@@ -83,17 +242,82 @@
 	 [f ai = Some bi] (when [f] returns [None], the corresponding element of
 	 [l] is discarded). *)
 
-	val find_map : ('a -> 'b option) -> 'a list -> 'b
-	(** [find_map pred list] finds the first element of [list] for which
-	    [pred element] returns [Some r].  It returns [r] immediately
-	    once found or raises [Not_found] if no element matches the
-	    predicate.  See also {!filter_map}. *)
+	val find_all : ('a -> bool) -> 'a list -> 'a list
+	  (** [find_all] is another name for {!List.filter}. *)
 
-	val split_nth : int -> 'a list -> 'a list * 'a list
-	(** [split_nth n l] returns two lists [l1] and [l2], [l1] containing the
+	val partition : ('a -> bool) -> 'a list -> 'a list * 'a list
+	  (** [partition p l] returns a pair of lists [(l1, l2)], where
+	      [l1] is the list of all the elements of [l] that
+	      satisfy the predicate [p], and [l2] is the list of all the
+	      elements of [l] that do not satisfy [p].
+	      The order of the elements in the input list is preserved. *)
+
+	val index_of : 'a -> 'a list -> int option
+        (** [index_of e l] returns the index of the first occurrence of [e]
+	    in [l], or [None] if there is no occurrence of [e] in [l] *)
+
+	val index_ofq : 'a -> 'a list -> int option
+        (** [index_ofq e l] behaves as [index_of e l] except it uses
+	    physical equality*)
+
+	val rindex_of : 'a -> 'a list -> int option
+        (** [rindex_of e l] returns the index of the last occurrence of [e]
+	    in [l], or [None] if there is no occurrence of [e] in [l] *)
+
+	val rindex_ofq : 'a -> 'a list -> int option
+        (** [rindex_ofq e l] behaves as [rindex_of e l] except it uses
+	    physical equality*)
+
+	val unique : ?cmp:('a -> 'a -> bool) -> 'a list -> 'a list
+	(** [unique cmp l] returns the list [l] without any duplicate element.
+	 Default comparator ( = ) is used if no comparison function specified. *)
+
+	  (**{6 Association lists}*)
+	val assoc : 'a -> ('a * 'b) list -> 'b
+	  (** [assoc a l] returns the value associated with key [a] in the list of
+	      pairs [l]. That is,
+	      [assoc a [ ...; (a,b); ...] = b]
+	      if [(a,b)] is the leftmost binding of [a] in list [l].
+	      Raise [Not_found] if there is no value associated with [a] in the
+	      list [l]. *)
+
+	val assoc_inv : 'b -> ('a * 'b) list -> 'a
+	  (** [assoc_inv b l] returns the key associated with value [b] in the list of
+	      pairs [l]. That is,
+	      [assoc b [ ...; (a,b); ...] = a]
+	      if [(a,b)] is the leftmost binding of [a] in list [l].
+	      Raise [Not_found] if there is no key associated with [b] in the
+	      list [l]. *)
+
+	val assq : 'a -> ('a * 'b) list -> 'b
+	  (** As {!assoc} but with physical equality *)
+
+	val mem_assoc : 'a -> ('a * 'b) list -> bool
+	  (** As {!assoc} but simply returns [true] if a binding exists, [false]
+	      otherwise. *)
+
+	val mem_assq : 'a -> ('a * 'b) list -> bool
+	  (** As {!mem_assoc} but with physical equality.*)
+
+	val remove_assoc : 'a -> ('a * 'b) list -> ('a * 'b) list
+	  (** [remove_assoc a l] returns the list of
+	      pairs [l] without the first pair with key [a], if any.
+	      Tail-recursive. *)
+
+	val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list
+	  (** Same as {!List.remove_assoc}, but uses physical equality instead
+	      of structural equality to compare keys.  Tail-recursive. *)
+
+
+	(** {6 List transformations}*)
+	val split_at : int -> 'a list -> 'a list * 'a list
+	(** [split_at n l] returns two lists [l1] and [l2], [l1] containing the
 	 first [n] elements of [l] and [l2] the others. Raise [Invalid_index] if
 	 [n] is outside of [l] size bounds. *)
 
+	val split_nth : int -> 'a list -> 'a list * 'a list
+	(** Obsolete. As [split_at]. *)
+
 	val remove : 'a list -> 'a -> 'a list
 	(** [remove l x] returns the list [l] without the first element [x] found
 	 or returns  [l] if no element is equal to [x]. Elements are compared
@@ -115,113 +339,90 @@
 	(** [drop n l] returns [l] without the first [n] elements, or the empty
 	 list if [l] have less than [n] elements. *)
 
-	val takewhile : ('a -> bool) -> 'a list -> 'a list
+	val take_while : ('a -> bool) -> 'a list -> 'a list
 	  (** [takewhile f xs] returns the first elements of list [xs]
 	      which satisfy the predicate [f]. *)
 
-	val dropwhile : ('a -> bool) -> 'a list -> 'a list
+	val takewhile :  ('a -> bool) -> 'a list -> 'a list
+	  (** obsolete, as {!take_while} *)
+
+	val drop_while : ('a -> bool) -> 'a list -> 'a list
 	  (** [dropwhile f xs] returns the list [xs] with the first
 	      elements satisfying the predicate [f] dropped. *)
 
-	(** {6 Enum functions} *)
+	val dropwhile : ('a -> bool) -> 'a list -> 'a list
+	  (** obsolete, as {!drop_while} *)
 
-	(** Enumerations are important in ExtLib, they are a good way to work with
-	 abstract enumeration of elements, regardless if they are located in a list,
-	 an array, or a file. *)
+	(** {6 Enum functions} 
+	    
+	    Abstraction layer.*)
 
 	val enum : 'a list -> 'a Enum.t
-	(** Returns an enumeration of the elements of a list. *)
+	(** Returns an enumeration of the elements of a list. This enumeration may
+	    be used to visit elements of the list in forward order (i.e. from the
+	    first element to the last one)*)
 
 	val of_enum : 'a Enum.t -> 'a list
-	(** Build a list from an enumeration. *)
+	(** Build a list from an enumeration. In the result, elements appear in the
+	    same order as they did in the source enumeration. *)
 
-	(** {6 Modified functions} *)
+	val backwards : 'a list -> 'a Enum.t
+	(** Returns an enumeration of the elements of a list. This enumeration may
+	    be used to visit elements of the list in backwards order (i.e. from the
+	    last element to the first one)*)
 
-	(** Some minor modifications have been made to the specification of some
-	 functions, especially concerning exceptions raised. *)
+	val of_backwards : 'a Enum.t -> 'a list
+	(** Build a list from an enumeration. The first element of the enumeration
+	    becomes the last element of the list, the second element of the enumeration
+	    becomes the second-to-last element of the list... *)
 
-	val hd : 'a list -> 'a
-	(** Returns the first element of the list or raise [Empty_list] if the
-	 list is empty. *)
 
-	val tl : 'a list -> 'a list
-	(** Returns the list without its first elements or raise [Empty_list] if
-	 the list is empty. *)
-
-	val nth : 'a list -> int -> 'a
-	(** [nth l n] returns the n-th element of the list [l] or raise
-	 [Invalid_index] is the index is outside of [l] bounds. *)
-
-	val sort : ?cmp:('a -> 'a -> int) -> 'a list -> 'a list
-	(** Sort the list using optional comparator (by default [compare]). *)
 
-	(** The following functions have been improved so all of them are
-	 tail-recursive. They have also been modified so they no longer
-	 raise [Invalid_arg] but [Different_list_size] when used on two
-	 lists having a different number of elements. *)
-
-	val map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
-	val iter2 : ('a -> 'b -> unit) -> 'a list -> 'b list -> unit
-	val fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b list -> 'c list -> 'a
-	val fold_right2 : ('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list -> 'c -> 'c
-	val for_all2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
-	val exists2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
-	val combine : 'a list -> 'b list -> ('a * 'b) list
-
-
-	(** {6 Improved functions} *)
-
-	(** The following functions have the same behavior as the [List]
-		module ones but are tail-recursive. That means they will not
-		cause a [Stack_overflow] when used on very long list.
-
-		The implementation might be a little more slow in bytecode,
-		but compiling in native code will not affect performances. *)
-
-	val map : ('a -> 'b) -> 'a list -> 'b list
-	val append : 'a list -> 'a list -> 'a list
-	val flatten : 'a list list -> 'a list
-	val concat : 'a list list -> 'a list
-	val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
-	val remove_assoc : 'a -> ('a * 'b) list -> ('a * 'b) list
-	val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list
+	  (** {6 List of pairs}*)
+	  
 	val split : ('a * 'b) list -> 'a list * 'b list
+	  (** Transform a list of pairs into a pair of lists:
+	      [split [(a1,b1); ...; (an,bn)]] is [([a1; ...; an], [b1; ...; bn])].
+	      Tail-recursive.
+	  *)
 
-	(** The following functions were already tail-recursive in the [List]
-		module but were using [List.rev] calls. The new implementations
-		have better performances. *)
-
-	val filter : ('a -> bool) -> 'a list -> 'a list
-	val find_all : ('a -> bool) -> 'a list -> 'a list
-	val partition : ('a -> bool) -> 'a list -> 'a list * 'a list
-
-	(** {6 Older functions} *)
-
-	(** These functions are already part of the Ocaml standard library
-		and have not been modified. Please refer to the Ocaml Manual for
-		documentation. *)
-
-	val length : 'a list -> int
-	val rev_append : 'a list -> 'a list -> 'a list
-	val rev : 'a list -> 'a list
-	val rev_map : ('a -> 'b) -> 'a list -> 'b list
-	val iter : ('a -> unit) -> 'a list -> unit
-	val fold_left : ('b -> 'a -> 'b) -> 'b -> 'a list -> 'b
-	val for_all : ('a -> bool) -> 'a list -> bool
-	val exists : ('a -> bool) -> 'a list -> bool
-	val find : ('a -> bool) -> 'a list -> 'a
-
-	val mem : 'a -> 'a list -> bool
-	val memq : 'a -> 'a list -> bool
-	val assoc : 'a -> ('a * 'b) list -> 'b
-	val assq : 'a -> ('a * 'b) list -> 'b
-	val mem_assoc : 'a -> ('a * 'b) list -> bool
-	val mem_assq : 'a -> ('a * 'b) list -> bool
+	val combine : 'a list -> 'b list -> ('a * 'b) list
+	  (** Transform a pair of lists into a list of pairs:
+	      [combine [a1; ...; an] [b1; ...; bn]] is
+	      [[(a1,b1); ...; (an,bn)]].
+	      Raise [Different_list_size] if the two lists
+	      have different lengths.  Tail-recursive. *)
+
+	(** {6 Utilities}*)
+	val make_compare : ('a -> 'a -> int) -> 'a list -> 'a list -> int
+	  (** [make_compare c] generates the lexicographical order on lists
+	      induced by [c]*)
 
+	val sort : ?cmp:('a -> 'a -> int) -> 'a list -> 'a list
+	  (** Sort the list using optional comparator (by default [compare]). *)
 
 	val stable_sort : ('a -> 'a -> int) -> 'a list -> 'a list
+	  (** Same as {!List.sort}, but the sorting algorithm is guaranteed to
+	      be stable (i.e. elements that compare equal are kept in their
+	      original order) .
+
+	      The current implementation uses Merge Sort. It runs in constant
+	      heap space and logarithmic stack space.
+	  *)
+	  
 	val fast_sort : ('a -> 'a -> int) -> 'a list -> 'a list
+	  (** Same as {!List.sort} or {!List.stable_sort}, whichever is faster
+	      on typical input. *)
+	  
 	val merge : ('a -> 'a -> int) -> 'a list -> 'a list -> 'a list
+	  (** Merge two lists:
+	      Assuming that [l1] and [l2] are sorted according to the
+	      comparison function [cmp], [merge cmp l1 l2] will return a
+	      sorted list containting all the elements of [l1] and [l2].
+	      If several elements compare equal, the elements of [l1] will be
+	      before the elements of [l2].
+	      Not tail-recursive (sum of the lengths of the arguments).
+	  *)
 
 	(** {6 Exceptions} *)
 
@@ -237,8 +438,10 @@
 	(** [Different_list_size] is raised when applying functions such as
 		[iter2] on two lists having different size. *)
 
-
-end
+	(** {6 Obsolete functions} *)
+	val nth : 'a list -> int -> 'a
+	(** Obsolete. As [at]. *)
+    end
 
 val ( @ ) : 'a list -> 'a list -> 'a list
 (** the new implementation for ( @ ) operator, see [List.append]. *)
diff -urN ocaml-extlib-read-only.orig/extlib/.svn/entries ocaml-extlib-read-only/extlib/.svn/entries
--- ocaml-extlib-read-only.orig/extlib/.svn/entries	2008-08-30 15:11:51.000000000 +0200
+++ ocaml-extlib-read-only/extlib/.svn/entries	2008-08-30 14:11:15.000000000 +0200
@@ -32,7 +32,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 99ee33dfaca5b476b251612af369253d
 2007-12-28T20:23:32.408536Z
 361
@@ -44,7 +44,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 35a8275bb8888c83d5c07899aa7cd718
 2007-12-28T20:23:32.408536Z
 361
@@ -56,7 +56,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 cd6f16b4f39c9c8e28377a9ed6f38d2c
 2004-07-26T19:11:14.000000Z
 231
@@ -68,7 +68,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 87f07e547cd66bfac4928e074ccc808d
 2007-12-28T20:23:32.408536Z
 361
@@ -80,7 +80,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 337baf3ae6550941e5e9c8b6c0f9373c
 2007-12-28T20:23:32.408536Z
 361
@@ -92,7 +92,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 890ecca9fa4a02cbfce25324827463b4
 2007-12-28T20:23:32.408536Z
 361
@@ -104,7 +104,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 3726001556e37089a57cce789671b045
 2007-12-28T20:23:32.408536Z
 361
@@ -116,7 +116,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 c6b23c4d7f4d327a4f04f6f4280816c1
 2006-03-07T11:07:22.000000Z
 346
@@ -128,7 +128,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 295efb5994c0045f0b2db8342ce742f1
 2005-05-07T08:51:04.000000Z
 317
@@ -140,7 +140,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 c722b2a6827a7fe53dbb2f607ef94125
 2007-04-08T17:23:41.000000Z
 351
@@ -152,7 +152,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 28f666c5cb1d03a34e7306f1cf44103c
 2005-02-08T10:04:19.000000Z
 308
@@ -164,7 +164,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 ef9e13836bc4ac05ac3170d9c8de592c
 2005-12-06T20:47:38.000000Z
 342
@@ -176,7 +176,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 2164faa5f23827a771429c96303cea51
 2008-04-23T12:03:57.089785Z
 380
@@ -188,7 +188,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 593d007dd9f2c22e6bd0bbea2d0d4bbf
 2004-09-20T14:09:33.000000Z
 257
@@ -200,7 +200,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 68e1fb912a508c90d5ce62578ece4a11
 2005-05-19T08:01:04.000000Z
 321
@@ -212,7 +212,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 08d15fdba87860e6879ace4101846003
 2006-02-20T16:04:42.000000Z
 344
@@ -224,7 +224,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 8e050d62b1bc6a3f6fdab6c0fb0b662d
 2004-05-06T09:44:41.000000Z
 199
@@ -236,7 +236,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 1236bbeadb622950524e504d01e75143
 2004-05-06T09:44:41.000000Z
 199
@@ -248,7 +248,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 364041e3fdd415c7d7d7fd4502b27b8e
 2007-12-28T20:23:32.408536Z
 361
@@ -260,7 +260,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 b6ff2f96d0de2d3001c304d13eb6135b
 2004-05-06T09:44:41.000000Z
 199
@@ -272,7 +272,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 6f609ef2adc95047b9c2cd07050394a0
 2005-05-07T08:51:04.000000Z
 317
@@ -284,7 +284,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 24766e36ac2fc85bdf70256e819e076a
 2004-10-26T06:58:20.000000Z
 262
@@ -296,7 +296,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 898b8daad72357979be000180f6b9a52
 2004-05-06T09:44:41.000000Z
 199
@@ -308,7 +308,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 d5c84916a0118eefacae63f44ba285ff
 2005-11-24T15:20:07.000000Z
 331
@@ -320,7 +320,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 bf250921a42c0cc75c2cb97758e8cdfb
 2005-02-17T23:51:06.000000Z
 312
@@ -332,7 +332,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 4150da91e7254bc321bb206ef240f881
 2004-05-06T09:44:41.000000Z
 199
@@ -344,7 +344,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 d7e7a3956a079c9dc0c63eb965d60231
 2006-03-06T20:53:18.000000Z
 345
@@ -356,7 +356,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 d4d740323afde7f715e0a65f280f1f03
 2007-11-27T19:46:53.000000Z
 352
@@ -368,7 +368,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 2cb67f54588406f885ca9d1e7aa14535
 2004-05-06T09:44:41.000000Z
 199
@@ -380,7 +380,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 b8ee9fc8e266faa70a62f2c7f1c1cce5
 2004-10-29T06:51:19.000000Z
 264
@@ -392,7 +392,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 c978a2326e4157eab96c905f0edbb2bf
 2004-05-06T09:44:41.000000Z
 199
@@ -404,7 +404,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 64b587ebdb7881dee0a8c95486b0d8b4
 2004-05-06T09:44:41.000000Z
 199
@@ -416,7 +416,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 d2b4287875082f6c7db677815efaa30a
 2008-02-02T09:32:49.231726Z
 377
@@ -428,7 +428,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 470d1ea88b0525e67b22081faebac6ab
 2005-05-19T10:48:33.000000Z
 322
@@ -440,7 +440,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 1fea2302f5132fdf00f1be95a470dd22
 2005-05-19T08:01:04.000000Z
 321
@@ -452,7 +452,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 e3c145db93ca187a345a825d8a771102
 2004-07-18T18:55:03.000000Z
 227
@@ -464,7 +464,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 b0e5cce623c9edfe7be9dcfa5345feda
 2004-05-06T09:44:41.000000Z
 199
@@ -476,7 +476,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 e175f675b4803db7f7c00f0e2173545b
 2006-10-11T16:24:42.000000Z
 348
@@ -488,7 +488,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 18eee13484de3553fe50c1a18c676459
 2004-05-06T09:44:41.000000Z
 199
@@ -500,7 +500,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 56fb3575c3cdb1c6b1b347a3280f1f6f
 2006-03-06T20:53:18.000000Z
 345
@@ -512,7 +512,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 abc642714df74739f43a3bf7b397f5fb
 2004-12-22T07:59:46.000000Z
 273
@@ -524,7 +524,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 4e700f79a816a7e85c755977da4a6b0e
 2004-05-06T09:44:41.000000Z
 199
@@ -536,7 +536,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 f32671fc0fa94dcc7afdf04ebe195e90
 2004-05-22T07:03:36.000000Z
 203
@@ -548,7 +548,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 95aba1b949f632b25fa7adb23b85f434
 2008-04-23T12:03:57.089785Z
 380
@@ -560,7 +560,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 1d9d64297b26eb729f95dc1fd3d43586
 2007-12-25T11:32:35.000000Z
 355
@@ -572,7 +572,7 @@
 
 
 
-2008-08-30T13:11:41.000000Z
+2008-08-28T12:33:26.000000Z
 63b9e3f062ed924f877f47bb73a0e7a9
 2005-12-07T13:47:19.000000Z
 343
diff -urN ocaml-extlib-read-only.orig/test/.svn/entries ocaml-extlib-read-only/test/.svn/entries
--- ocaml-extlib-read-only.orig/test/.svn/entries	2008-08-30 15:11:51.000000000 +0200
+++ ocaml-extlib-read-only/test/.svn/entries	2008-08-30 14:11:16.000000000 +0200
@@ -32,7 +32,7 @@
 
 
 
-2008-08-30T13:11:38.000000Z
+2008-08-28T12:33:24.000000Z
 02f4ced36486a952b32f40a1318d1241
 2005-11-25T10:22:19.000000Z
 341
@@ -44,7 +44,7 @@
 
 
 
-2008-08-30T13:11:38.000000Z
+2008-08-28T12:33:24.000000Z
 76da4f9021b2620a91978c15c58ec90c
 2004-12-23T22:18:45.000000Z
 285
@@ -56,7 +56,7 @@
 
 
 
-2008-08-30T13:11:38.000000Z
+2008-08-28T12:33:24.000000Z
 7a65ec4cd15861fbddfd3752e01a566b
 2007-12-30T19:53:02.568798Z
 375
@@ -68,7 +68,7 @@
 
 
 
-2008-08-30T13:11:38.000000Z
+2008-08-28T12:33:24.000000Z
 4045f1e0d443cf020e6e414a515e4318
 2007-04-08T11:57:44.000000Z
 349
@@ -80,7 +80,7 @@
 
 
 
-2008-08-30T13:11:38.000000Z
+2008-08-28T12:33:24.000000Z
 a8595307fa012a4f3b988f5185059e3a
 2004-12-28T12:12:17.000000Z
 302
@@ -92,7 +92,7 @@
 
 
 
-2008-08-30T13:11:38.000000Z
+2008-08-28T12:33:24.000000Z
 8d3d4b7d013a4197c7e0dc4e41b498ad
 2004-12-27T21:51:20.000000Z
 298
@@ -104,7 +104,7 @@
 
 
 
-2008-08-30T13:11:38.000000Z
+2008-08-28T12:33:24.000000Z
 f40e7d33885a0fa12a73d7f6c69892a9
 2005-03-02T19:25:44.000000Z
 315
@@ -116,7 +116,7 @@
 
 
 
-2008-08-30T13:11:38.000000Z
+2008-08-28T12:33:24.000000Z
 24c7132b9c1fee2b5070a1a880dec428
 2004-12-27T19:16:17.000000Z
 296
@@ -128,7 +128,7 @@
 
 
 
-2008-08-30T13:11:38.000000Z
+2008-08-28T12:33:24.000000Z
 8b1ef9caf456924251711880f17b3ba8
 2005-02-15T10:11:27.000000Z
 310
@@ -140,7 +140,7 @@
 
 
 
-2008-08-30T13:11:38.000000Z
+2008-08-28T12:33:24.000000Z
 95f574a8bd1756a9a410994dff4fecc9
 2005-01-15T13:10:34.000000Z
 306
@@ -152,7 +152,7 @@
 
 
 
-2008-08-30T13:11:38.000000Z
+2008-08-28T12:33:24.000000Z
 5a987c0aa0de3883ff3415978c1d6414
 2007-04-08T11:57:44.000000Z
 349
@@ -164,7 +164,7 @@
 
 
 
-2008-08-30T13:11:38.000000Z
+2008-08-28T12:33:24.000000Z
 4f74305685d74ea7eb4095d21c03977c
 2007-04-08T17:18:47.000000Z
 350
@@ -176,7 +176,7 @@
 
 
 
-2008-08-30T13:11:38.000000Z
+2008-08-28T12:33:24.000000Z
 18083c760fe60825217ff15fddbd77e7
 2004-12-21T06:30:55.000000Z
 272
@@ -188,7 +188,7 @@
 
 
 
-2008-08-30T13:11:38.000000Z
+2008-08-28T12:33:24.000000Z
 100e2fcbf5cafabc63241e8a5b67e7fd
 2007-12-25T11:29:56.000000Z
 354
@@ -203,7 +203,7 @@
 
 
 
-2008-08-30T13:11:38.000000Z
+2008-08-28T12:33:24.000000Z
 845b53b567667c6aa9ca4e1e20c41128
 2004-12-24T10:49:00.000000Z
 287
@@ -215,7 +215,7 @@
 
 
 
-2008-08-30T13:11:38.000000Z
+2008-08-28T12:33:24.000000Z
 1d9ace098b2a2b02be7908ecbeae79d0
 2007-12-30T19:53:02.568798Z
 375
@@ -227,7 +227,7 @@
 
 
 
-2008-08-30T13:11:38.000000Z
+2008-08-28T12:33:24.000000Z
 d69aceb57a22dbbe2f0e586b21cca669
 2007-12-25T12:02:18.000000Z
 357
@@ -239,7 +239,7 @@
 
 
 
-2008-08-30T13:11:38.000000Z
+2008-08-28T12:33:24.000000Z
 14aed34e8eb25c7e9fdbeae72b904b35
 2008-04-23T18:09:27.770031Z
 381
@@ -251,7 +251,7 @@
 
 
 
-2008-08-30T13:11:38.000000Z
+2008-08-28T12:33:24.000000Z
 38e25db1b067e5f5749e74c94b00be31
 2007-12-30T19:53:02.568798Z
 375
@@ -263,7 +263,7 @@
 
 
 
-2008-08-30T13:11:38.000000Z
+2008-08-28T12:33:24.000000Z
 945e851a2d06d0a92e430ac75a6ae871
 2007-11-27T19:46:53.000000Z
 352
diff -urN ocaml-extlib-read-only.orig/test/util/zlib-test/.svn/entries ocaml-extlib-read-only/test/util/zlib-test/.svn/entries
--- ocaml-extlib-read-only.orig/test/util/zlib-test/.svn/entries	2008-08-30 15:11:51.000000000 +0200
+++ ocaml-extlib-read-only/test/util/zlib-test/.svn/entries	2008-08-30 14:11:16.000000000 +0200
@@ -32,7 +32,7 @@
 
 
 
-2008-08-30T13:11:37.000000Z
+2008-08-28T12:33:23.000000Z
 e466f98334d72d431e31a5d313667dfa
 2007-12-25T11:55:54.000000Z
 356
@@ -45,7 +45,7 @@
 
 
 
-2008-08-30T13:11:37.000000Z
+2008-08-28T12:33:23.000000Z
 93cb00f8763621d80d39b54902fdab3b
 2007-12-25T12:04:42.000000Z
 358
@@ -57,7 +57,7 @@
 
 
 
-2008-08-30T13:11:37.000000Z
+2008-08-28T12:33:23.000000Z
 ff9873126cd57adcc14c992c7d27a733
 2007-12-25T11:55:54.000000Z
 356