Ajout des fonctions find, partition, find_all

git-svn-id: http://caml.inria.fr/svn/ocaml/trunk@2244 f963ae5c-01c2-4b8c-9fe0-0dff7051ff02

2 files changed, 36 insertions, 2 deletions

diff --git a/stdlib/list.ml b/stdlib/list.ml
index bac2dd1da..90cee4303 100644
--- a/stdlib/list.ml
+++ b/stdlib/list.ml
@@ -144,6 +144,22 @@ let rec removeq x = function
   | [] -> []
   | (a, b as pair) :: l -> if a == x then l else pair :: removeq x l
 
+let rec find p = function
+  | [] -> raise Not_found
+  | x :: l -> if p x then x else find p l
+
+let find_all p =
+  let rec find accu = function
+  | [] -> rev accu
+  | x :: l -> if p x then find (x :: accu) l else find accu l in
+  find []
+
+let rec partition p l =
+  let rec part yes no = function
+  | [] -> (rev yes, rev no)
+  | x :: l -> if p x then part (x :: yes) no l else part yes (x :: no) l in
+  part [] [] l
+
 let rec split = function
     [] -> ([], [])
   | (x,y)::l ->
diff --git a/stdlib/list.mli b/stdlib/list.mli
index 0c0a41ccf..cdd92b8c6 100644
--- a/stdlib/list.mli
+++ b/stdlib/list.mli
@@ -82,11 +82,11 @@ val fold_right2 : ('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list -> 'c -> 'c
 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)]. *)
+           [(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) or (p a2) or ... or (p an)]. *)
+           [(p a1) || (p a2) || ... || (p an)]. *)
 val for_all2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
 val exists2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
         (* Same as [for_all] and [exists], but for a two-argument predicate.
@@ -99,6 +99,24 @@ val memq : 'a -> 'a list -> bool
         (* Same as [mem], but uses physical equality instead of structural
            equality to compare list elements. *)
 
+(** List searching *)
+
+val find : ('a -> bool) -> 'a list -> 'a
+        (* [find p l] returns the first element of the list [l]
+           that satisfies the predicate [p].
+           Raise [Not_found] if there is no value that satisfies [p] in the
+           list [l]. *)
+
+val find_all : ('a -> bool) -> 'a list -> 'a list
+        (* [find_all p l] returns all the elements of the list [l]
+           that satisfies the predicate [p]. *)
+
+val partition : ('a -> bool) -> 'a list -> 'a list * 'a list
+        (* [partition p l] returns a pair of lists [(l1, l2)], such
+        that [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]. *)
+
 (** Association lists *)
 
 val assoc : 'a -> ('a * 'b) list -> 'b