Merge PR #7177: Unifying names of "smart" combinators + adding combinators in CArray

9 files changed, 390 insertions, 156 deletions

diff --git a/clib/cArray.ml b/clib/cArray.ml
index 071f4689bd..b26dae7298 100644
--- a/clib/cArray.ml
+++ b/clib/cArray.ml
@@ -50,7 +50,9 @@ sig
   val map_of_list : ('a -> 'b) -> 'a list -> 'b array
   val chop : int -> 'a array -> 'a array * 'a array
   val smartmap : ('a -> 'a) -> 'a array -> 'a array
+  [@@ocaml.deprecated "Same as [Smart.map]"]
   val smartfoldmap : ('r -> 'a -> 'r * 'a) -> 'r -> 'a array -> 'r * 'a array
+  [@@ocaml.deprecated "Same as [Smart.fold_left_map]"]
   val map2 : ('a -> 'b -> 'c) -> 'a array -> 'b array -> 'c array
   val map2_i : (int -> 'a -> 'b -> 'c) -> 'a array -> 'b array -> 'c array
   val map3 :
@@ -72,6 +74,25 @@ sig
   val rev_of_list : 'a list -> 'a array
   val rev_to_list : 'a array -> 'a list
   val filter_with : bool list -> 'a array -> 'a array
+  module Smart :
+  sig
+    val map : ('a -> 'a) -> 'a array -> 'a array
+    val map2 : ('a -> 'b -> 'b) -> 'a array -> 'b array -> 'b array
+    val fold_left_map : ('a -> 'b -> 'a * 'b) -> 'a -> 'b array -> 'a * 'b array
+    val fold_left2_map : ('a -> 'b -> 'c -> 'a * 'c) -> 'a -> 'b array -> 'c array -> 'a * 'c array
+  end
+  module Fun1 :
+  sig
+    val map : ('r -> 'a -> 'b) -> 'r -> 'a array -> 'b array
+    val smartmap : ('r -> 'a -> 'a) -> 'r -> 'a array -> 'a array
+    [@@ocaml.deprecated "Same as [Fun1.Smart.map]"]
+    val iter : ('r -> 'a -> unit) -> 'r -> 'a array -> unit
+    val iter2 : ('r -> 'a -> 'b -> unit) -> 'r -> 'a array -> 'b array -> unit
+    module Smart :
+    sig
+      val map : ('r -> 'a -> 'a) -> 'r -> 'a array -> 'a array
+    end
+  end
 end
 
 include Array
@@ -326,72 +347,6 @@ let chop n v =
   if n > vlen then failwith "Array.chop";
   (Array.sub v 0 n, Array.sub v n (vlen-n))
 
-(* If none of the elements is changed by f we return ar itself.
-   The while loop looks for the first such an element.
-   If found, we break here and the new array is produced,
-   but f is not re-applied to elements that are already checked *)
-let smartmap f (ar : 'a array) =
-  let len = Array.length ar in
-  let i = ref 0 in
-  let break = ref true in
-  let temp = ref None in
-  while !break && (!i < len) do
-    let v = Array.unsafe_get ar !i in
-    let v' = f v in
-    if v == v' then incr i
-    else begin
-      break := false;
-      temp := Some v';
-    end
-  done;
-  if !i < len then begin
-    (** The array is not the same as the original one *)
-    let ans : 'a array = Array.copy ar in
-    let v = match !temp with None -> assert false | Some x -> x in
-    Array.unsafe_set ans !i v;
-    incr i;
-    while !i < len do
-      let v = Array.unsafe_get ans !i in
-      let v' = f v in
-      if v != v' then Array.unsafe_set ans !i v';
-      incr i
-    done;
-    ans
-  end else ar
-
-(** Same as [smartmap] but threads a state meanwhile *)
-let smartfoldmap f accu (ar : 'a array) =
-  let len = Array.length ar in
-  let i = ref 0 in
-  let break = ref true in
-  let r = ref accu in
-  (** This variable is never accessed unset *)
-  let temp = ref None in
-  while !break && (!i < len) do
-    let v = Array.unsafe_get ar !i in
-    let (accu, v') = f !r v in
-    r := accu;
-    if v == v' then incr i
-    else begin
-      break := false;
-      temp := Some v';
-    end
-  done;
-  if !i < len then begin
-    let ans : 'a array = Array.copy ar in
-    let v = match !temp with None -> assert false | Some x -> x in
-    Array.unsafe_set ans !i v;
-    incr i;
-    while !i < len do
-      let v = Array.unsafe_get ar !i in
-      let (accu, v') = f !r v in
-      r := accu;
-      if v != v' then Array.unsafe_set ans !i v';
-      incr i
-    done;
-    !r, ans
-  end else !r, ar
-
 let map2 f v1 v2 =
   let len1 = Array.length v1 in
   let len2 = Array.length v2 in
@@ -508,29 +463,53 @@ let rev_to_list a =
 let filter_with filter v =
   Array.of_list (CList.filter_with filter (Array.to_list v))
 
-module Fun1 =
+module Smart =
 struct
 
-  let map f arg v = match v with
-  | [| |] -> [| |]
-  | _ ->
-    let len = Array.length v in
-    let x0 = Array.unsafe_get v 0 in
-    let ans = Array.make len (f arg x0) in
-    for i = 1 to pred len do
-      let x = Array.unsafe_get v i in
-      Array.unsafe_set ans i (f arg x)
+  (* If none of the elements is changed by f we return ar itself.
+     The while loop looks for the first such an element.
+     If found, we break here and the new array is produced,
+     but f is not re-applied to elements that are already checked *)
+  let map f (ar : 'a array) =
+    let len = Array.length ar in
+    let i = ref 0 in
+    let break = ref true in
+    let temp = ref None in
+    while !break && (!i < len) do
+      let v = Array.unsafe_get ar !i in
+      let v' = f v in
+      if v == v' then incr i
+      else begin
+        break := false;
+        temp := Some v';
+      end
     done;
-    ans
+    if !i < len then begin
+      (** The array is not the same as the original one *)
+      let ans : 'a array = Array.copy ar in
+      let v = match !temp with None -> assert false | Some x -> x in
+      Array.unsafe_set ans !i v;
+      incr i;
+      while !i < len do
+        let v = Array.unsafe_get ans !i in
+        let v' = f v in
+        if v != v' then Array.unsafe_set ans !i v';
+        incr i
+      done;
+      ans
+    end else ar
 
-  let smartmap f arg (ar : 'a array) =
+  let map2 f aux_ar ar =
     let len = Array.length ar in
+    let aux_len = Array.length aux_ar in
+    let () = if not (Int.equal len aux_len) then invalid_arg "Array.Smart.map2" in
     let i = ref 0 in
     let break = ref true in
     let temp = ref None in
     while !break && (!i < len) do
       let v = Array.unsafe_get ar !i in
-      let v' = f arg v in
+      let w = Array.unsafe_get aux_ar !i in
+      let v' = f w v in
       if v == v' then incr i
       else begin
         break := false;
@@ -545,13 +524,105 @@ struct
       incr i;
       while !i < len do
         let v = Array.unsafe_get ans !i in
-        let v' = f arg v in
+        let w = Array.unsafe_get aux_ar !i in
+        let v' = f w v in
         if v != v' then Array.unsafe_set ans !i v';
         incr i
       done;
       ans
     end else ar
 
+  (** Same as [Smart.map] but threads a state meanwhile *)
+  let fold_left_map f accu (ar : 'a array) =
+    let len = Array.length ar in
+    let i = ref 0 in
+    let break = ref true in
+    let r = ref accu in
+    (** This variable is never accessed unset *)
+    let temp = ref None in
+    while !break && (!i < len) do
+      let v = Array.unsafe_get ar !i in
+      let (accu, v') = f !r v in
+      r := accu;
+      if v == v' then incr i
+      else begin
+        break := false;
+        temp := Some v';
+      end
+    done;
+    if !i < len then begin
+      let ans : 'a array = Array.copy ar in
+      let v = match !temp with None -> assert false | Some x -> x in
+      Array.unsafe_set ans !i v;
+      incr i;
+      while !i < len do
+        let v = Array.unsafe_get ar !i in
+        let (accu, v') = f !r v in
+        r := accu;
+        if v != v' then Array.unsafe_set ans !i v';
+        incr i
+      done;
+      !r, ans
+    end else !r, ar
+
+  (** Same as [Smart.map2] but threads a state meanwhile *)
+  let fold_left2_map f accu aux_ar ar =
+    let len = Array.length ar in
+    let aux_len = Array.length aux_ar in
+    let () = if not (Int.equal len aux_len) then invalid_arg "Array.Smart.fold_left2_map" in
+    let i = ref 0 in
+    let break = ref true in
+    let r = ref accu in
+    (** This variable is never accessed unset *)
+    let temp = ref None in
+    while !break && (!i < len) do
+      let v = Array.unsafe_get ar !i in
+      let w = Array.unsafe_get aux_ar !i in
+      let (accu, v') = f !r w v in
+      r := accu;
+      if v == v' then incr i
+      else begin
+        break := false;
+        temp := Some v';
+      end
+    done;
+    if !i < len then begin
+      let ans : 'a array = Array.copy ar in
+      let v = match !temp with None -> assert false | Some x -> x in
+      Array.unsafe_set ans !i v;
+      incr i;
+      while !i < len do
+        let v = Array.unsafe_get ar !i in
+        let w = Array.unsafe_get aux_ar !i in
+        let (accu, v') = f !r w v in
+        r := accu;
+        if v != v' then Array.unsafe_set ans !i v';
+        incr i
+      done;
+      !r, ans
+    end else !r, ar
+
+end
+
+(* Deprecated aliases *)
+let smartmap = Smart.map
+let smartfoldmap = Smart.fold_left_map
+
+module Fun1 =
+struct
+
+  let map f arg v = match v with
+  | [| |] -> [| |]
+  | _ ->
+    let len = Array.length v in
+    let x0 = Array.unsafe_get v 0 in
+    let ans = Array.make len (f arg x0) in
+    for i = 1 to pred len do
+      let x = Array.unsafe_get v i in
+      Array.unsafe_set ans i (f arg x)
+    done;
+    ans
+
   let iter f arg v =
     let len = Array.length v in
     for i = 0 to pred len do
@@ -559,4 +630,50 @@ struct
       f arg x
     done
 
+  let iter2 f arg v1 v2 =
+    let len1 = Array.length v1 in
+    let len2 = Array.length v2 in
+    let () = if not (Int.equal len2 len1) then invalid_arg "Array.Fun1.iter2" in
+    for i = 0 to pred len1 do
+      let x1 = uget v1 i in
+      let x2 = uget v2 i in
+      f arg x1 x2
+    done
+
+  module Smart =
+  struct
+
+    let map f arg (ar : 'a array) =
+      let len = Array.length ar in
+      let i = ref 0 in
+      let break = ref true in
+      let temp = ref None in
+      while !break && (!i < len) do
+        let v = Array.unsafe_get ar !i in
+        let v' = f arg v in
+        if v == v' then incr i
+        else begin
+          break := false;
+          temp := Some v';
+        end
+      done;
+      if !i < len then begin
+        (** The array is not the same as the original one *)
+        let ans : 'a array = Array.copy ar in
+        let v = match !temp with None -> assert false | Some x -> x in
+        Array.unsafe_set ans !i v;
+        incr i;
+        while !i < len do
+          let v = Array.unsafe_get ans !i in
+          let v' = f arg v in
+          if v != v' then Array.unsafe_set ans !i v';
+          incr i
+        done;
+        ans
+      end else ar
+
+  end
+
+  let smartmap = Smart.map
+
 end
diff --git a/clib/cArray.mli b/clib/cArray.mli
index 9c2f521f4a..8bf33f82f9 100644
--- a/clib/cArray.mli
+++ b/clib/cArray.mli
@@ -83,13 +83,14 @@ sig
       Raise [Failure "Array.chop"] if [i] is not a valid index. *)
 
   val smartmap : ('a -> 'a) -> 'a array -> 'a array
-  (** [smartmap f a] behaves as [map f a] but returns [a] instead of a copy when
-      [f x == x] for all [x] in [a]. *)
+  [@@ocaml.deprecated "Same as [Smart.map]"]
 
   val smartfoldmap : ('r -> 'a -> 'r * 'a) -> 'r -> 'a array -> 'r * 'a array
-  (** Same as [smartmap] but threads an additional state left-to-right. *)
+  [@@ocaml.deprecated "Same as [Smart.fold_left_map]"]
 
   val map2 : ('a -> 'b -> 'c) -> 'a array -> 'b array -> 'c array
+  (** See also [Smart.map2] *)
+
   val map2_i : (int -> 'a -> 'b -> 'c) -> 'a array -> 'b array -> 'c array
   val map3 :
     ('a -> 'b -> 'c -> 'd) -> 'a array -> 'b array -> 'c array -> 'd array
@@ -102,13 +103,13 @@ sig
 
   val fold_left_map : ('a -> 'b -> 'a * 'c) -> 'a -> 'b array -> 'a * 'c array
   (** [fold_left_map f e_0 [|l_1...l_n|] = e_n,[|k_1...k_n|]]
-    where [(e_i,k_i)=f e_{i-1} l_i] *)
+    where [(e_i,k_i)=f e_{i-1} l_i]; see also [Smart.fold_left_map] *)
 
   val fold_right_map : ('a -> 'c -> 'b * 'c) -> 'a array -> 'c -> 'b array * 'c
   (** Same, folding on the right *)
 
   val fold_left2_map : ('a -> 'b -> 'c -> 'a * 'd) -> 'a -> 'b array -> 'c array -> 'a * 'd array
-  (** Same with two arrays, folding on the left *)
+  (** Same with two arrays, folding on the left; see also [Smart.fold_left2_map] *)
 
   val fold_right2_map : ('a -> 'b -> 'c -> 'd * 'c) -> 'a array -> 'b array -> 'c -> 'd array * 'c
   (** Same with two arrays, folding on the left *)
@@ -137,23 +138,57 @@ sig
   (** [filter_with b a] selects elements of [a] whose corresponding element in
       [b] is [true].  Raise [Invalid_argument _] when sizes differ. *)
 
+  module Smart :
+  sig
+    val map : ('a -> 'a) -> 'a array -> 'a array
+    (** [Smart.map f a] behaves as [map f a] but returns [a] instead of a copy when
+        [f x == x] for all [x] in [a]. *)
+
+    val map2 : ('a -> 'b -> 'b) -> 'a array -> 'b array -> 'b array
+    (** [Smart.map2 f a b] behaves as [map2 f a b] but returns [a] instead of a copy when
+        [f x y == y] for all [x] in [a] and [y] in [b] pointwise. *)
+
+    val fold_left_map : ('a -> 'b -> 'a * 'b) -> 'a -> 'b array -> 'a * 'b array
+    (** [Smart.fold_left_mapf a b] behaves as [fold_left_map] but
+        returns [b] as second component instead of a copy of [b] when
+        the output array is pointwise the same as the input array [b] *)
+
+    val fold_left2_map : ('a -> 'b -> 'c -> 'a * 'c) -> 'a -> 'b array -> 'c array -> 'a * 'c array
+    (** [Smart.fold_left2_map f a b c] behaves as [fold_left2_map] but
+        returns [c] as second component instead of a copy of [c] when
+        the output array is pointwise the same as the input array [c] *)
+
+  end
+  (** The functions defined in this module are optimized specializations
+      of the main ones, when the returned array is of same type as one of
+      the original array. *)
+
+  module Fun1 :
+  sig
+    val map : ('r -> 'a -> 'b) -> 'r -> 'a array -> 'b array
+    (** [Fun1.map f x v = map (f x) v] *)
+
+    val smartmap : ('r -> 'a -> 'a) -> 'r -> 'a array -> 'a array
+    [@@ocaml.deprecated "Same as [Fun1.Smart.map]"]
+
+    val iter : ('r -> 'a -> unit) -> 'r -> 'a array -> unit
+    (** [Fun1.iter f x v = iter (f x) v] *)
+
+    val iter2 : ('r -> 'a -> 'b -> unit) -> 'r -> 'a array -> 'b array -> unit
+    (** [Fun1.iter2 f x v1 v2 = iter (f x) v1 v2] *)
+
+    module Smart :
+    sig
+      val map : ('r -> 'a -> 'a) -> 'r -> 'a array -> 'a array
+      (** [Fun1.Smart.map f x v = Smart.map (f x) v] *)
+    end
+
+  end
+  (** The functions defined in this module are the same as the main ones, except
+      that they are all higher-order, and their function arguments have an
+      additional parameter. This allows us to prevent closure creation in critical
+      cases. *)
+
 end
 
 include ExtS
-
-module Fun1 :
-sig
-  val map : ('r -> 'a -> 'b) -> 'r -> 'a array -> 'b array
-  (** [Fun1.map f x v = map (f x) v] *)
-
-  val smartmap : ('r -> 'a -> 'a) -> 'r -> 'a array -> 'a array
-  (** [Fun1.smartmap f x v = smartmap (f x) v] *)
-
-  val iter : ('r -> 'a -> unit) -> 'r -> 'a array -> unit
-  (** [Fun1.iter f x v = iter (f x) v] *)
-
-end
-(** The functions defined in this module are the same as the main ones, except
-    that they are all higher-order, and their function arguments have an
-    additional parameter. This allows us to prevent closure creation in critical
-    cases. *)
diff --git a/clib/cList.ml b/clib/cList.ml
index 8727f46965..7621793d46 100644
--- a/clib/cList.ml
+++ b/clib/cList.ml
@@ -39,6 +39,7 @@ sig
   val map_filter_i : (int -> 'a -> 'b option) -> 'a list -> 'b list
   val filter_with : bool list -> 'a list -> 'a list
   val smartmap : ('a -> 'a) -> 'a list -> 'a list
+  [@@ocaml.deprecated "Same as [Smart.map]"]
   val map_left : ('a -> 'b) -> 'a list -> 'b list
   val map_i : (int -> 'a -> 'b) -> int -> 'a list -> 'b list
   val map2_i :
@@ -53,6 +54,7 @@ sig
     (int -> 'a -> bool) -> 'a list -> 'a list * 'a list
   val map_of_array : ('a -> 'b) -> 'a array -> 'b list
   val smartfilter : ('a -> bool) -> 'a list -> 'a list
+  [@@ocaml.deprecated "Same as [Smart.map]"]
   val extend : bool list -> 'a -> 'a list -> 'a list
   val count : ('a -> bool) -> 'a list -> int
   val index : 'a eq -> 'a -> 'a list -> int
@@ -117,6 +119,12 @@ sig
     ('a -> 'b -> 'b option) -> 'b -> 'a list list -> 'b list
   val factorize_left : 'a eq -> ('a * 'b) list -> ('a * 'b list) list
 
+  module Smart :
+  sig
+    val map : ('a -> 'a) -> 'a list -> 'a list
+    val filter : ('a -> bool) -> 'a list -> 'a list
+  end
+
   module type MonoS = sig
     type elt
     val equal : elt list -> elt list -> bool
@@ -365,13 +373,6 @@ let assign l n e =
   in
   assrec [] l n
 
-let rec smartmap f l = match l with
-    [] -> l
-  | h::tl ->
-      let h' = f h and tl' = smartmap f tl in
-        if h'==h && tl'==tl then l
-        else h'::tl'
-
 let map_left = map
 
 let map2_i f i l1 l2 =
@@ -398,15 +399,6 @@ let map4 f l1 l2 l3 l4 =
   in
   map (l1,l2,l3,l4)
 
-let rec smartfilter f l = match l with
-    [] -> l
-  | h::tl ->
-      let tl' = smartfilter f tl in
-        if f h then
-          if tl' == tl then l
-          else h :: tl'
-        else tl'
-
 let rec extend l a l' = match l,l' with
   | true::l, b::l' -> b :: extend l a l'
   | false::l, l' -> a :: extend l a l'
@@ -896,6 +888,30 @@ let rec factorize_left cmp = function
       (a,(b::List.map snd al)) :: factorize_left cmp l'
   | [] -> []
 
+module Smart =
+struct
+
+  let rec map f l = match l with
+    [] -> l
+  | h::tl ->
+      let h' = f h and tl' = map f tl in
+        if h'==h && tl'==tl then l
+        else h'::tl'
+
+  let rec filter f l = match l with
+    [] -> l
+  | h::tl ->
+      let tl' = filter f tl in
+        if f h then
+          if tl' == tl then l
+          else h :: tl'
+        else tl'
+
+end
+
+let smartmap = Smart.map
+let smartfilter = Smart.filter
+
 module type MonoS = sig
   type elt
   val equal : elt list -> elt list -> bool
diff --git a/clib/cList.mli b/clib/cList.mli
index fd6d6a158a..b3c1510983 100644
--- a/clib/cList.mli
+++ b/clib/cList.mli
@@ -75,8 +75,7 @@ sig
       [b] is [true]. Raise [Invalid_argument _] when sizes differ. *)
 
   val smartmap : ('a -> 'a) -> 'a list -> 'a list
-  (** [smartmap f [a1...an] = List.map f [a1...an]] but if for all i
-    [f ai == ai], then [smartmap f l == l] *)
+  [@@ocaml.deprecated "Same as [Smart.map]"]
 
   val map_left : ('a -> 'b) -> 'a list -> 'b list
   (** As [map] but ensures the left-to-right order of evaluation. *)
@@ -97,8 +96,7 @@ sig
   (** [map_of_array f a] behaves as [List.map f (Array.to_list a)] *)
 
   val smartfilter : ('a -> bool) -> 'a list -> 'a list
-  (** [smartfilter f [a1...an] = List.filter f [a1...an]] but if for all i
-    [f ai = true], then [smartfilter f l == l] *)
+  [@@ocaml.deprecated "Same as [Smart.filter]"]
 
   val extend : bool list -> 'a -> 'a list -> 'a list
 (** [extend l a [a1..an]] assumes that the number of [true] in [l] is [n];
@@ -258,6 +256,17 @@ sig
 
   val factorize_left : 'a eq -> ('a * 'b) list -> ('a * 'b list) list
 
+  module Smart :
+  sig
+    val map : ('a -> 'a) -> 'a list -> 'a list
+    (** [Smart.map f [a1...an] = List.map f [a1...an]] but if for all i
+        [f ai == ai], then [Smart.map f l == l] *)
+
+    val filter : ('a -> bool) -> 'a list -> 'a list
+    (** [Smart.filter f [a1...an] = List.filter f [a1...an]] but if for all i
+        [f ai = true], then [Smart.filter f l == l] *)
+  end
+
   module type MonoS = sig
     type elt
     val equal : elt list -> elt list -> bool
diff --git a/clib/cMap.ml b/clib/cMap.ml
index 373e3f8fda..f6e52594be 100644
--- a/clib/cMap.ml
+++ b/clib/cMap.ml
@@ -35,8 +35,15 @@ sig
   val fold_left : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
   val fold_right : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
   val smartmap : ('a -> 'a) -> 'a t -> 'a t
+  (** [@@ocaml.deprecated "Same as [Smart.map]"] *)
   val smartmapi : (key -> 'a -> 'a) -> 'a t -> 'a t
+  (** [@@ocaml.deprecated "Same as [Smart.mapi]"] *)
   val height : 'a t -> int
+  module Smart :
+  sig
+    val map : ('a -> 'a) -> 'a t -> 'a t
+    val mapi : (key -> 'a -> 'a) -> 'a t -> 'a t
+  end
   module Unsafe :
   sig
     val map : (key -> 'a -> key * 'b) -> 'a t -> 'b t
@@ -59,8 +66,15 @@ sig
   val fold_left : (M.t -> 'a -> 'b -> 'b) -> 'a map -> 'b -> 'b
   val fold_right : (M.t -> 'a -> 'b -> 'b) -> 'a map -> 'b -> 'b
   val smartmap : ('a -> 'a) -> 'a map -> 'a map
+  (** [@@ocaml.deprecated "Same as [Smart.map]"] *)
   val smartmapi : (M.t -> 'a -> 'a) -> 'a map -> 'a map
+  (** [@@ocaml.deprecated "Same as [Smart.mapi]"] *)
   val height : 'a map -> int
+  module Smart :
+  sig
+    val map : ('a -> 'a) -> 'a map -> 'a map
+    val mapi : (M.t -> 'a -> 'a) -> 'a map -> 'a map
+  end
   module Unsafe :
   sig
     val map : (M.t -> 'a -> M.t * 'b) -> 'a map -> 'b map
@@ -154,28 +168,36 @@ struct
     let accu = f k v (fold_right f r accu) in
     fold_right f l accu
 
-  let rec smartmap f (s : 'a map) = match map_prj s with
-  | MEmpty -> map_inj MEmpty
-  | MNode (l, k, v, r, h) ->
-    let l' = smartmap f l in
-    let r' = smartmap f r in
-    let v' = f v in
-    if l == l' && r == r' && v == v' then s
-    else map_inj (MNode (l', k, v', r', h))
-
-  let rec smartmapi f (s : 'a map) = match map_prj s with
-  | MEmpty -> map_inj MEmpty
-  | MNode (l, k, v, r, h) ->
-    let l' = smartmapi f l in
-    let r' = smartmapi f r in
-    let v' = f k v in
-    if l == l' && r == r' && v == v' then s
-    else map_inj (MNode (l', k, v', r', h))
-
   let height s = match map_prj s with
   | MEmpty -> 0
   | MNode (_, _, _, _, h) -> h
 
+  module Smart =
+  struct
+
+    let rec map f (s : 'a map) = match map_prj s with
+    | MEmpty -> map_inj MEmpty
+    | MNode (l, k, v, r, h) ->
+      let l' = map f l in
+      let r' = map f r in
+      let v' = f v in
+      if l == l' && r == r' && v == v' then s
+      else map_inj (MNode (l', k, v', r', h))
+
+    let rec mapi f (s : 'a map) = match map_prj s with
+    | MEmpty -> map_inj MEmpty
+    | MNode (l, k, v, r, h) ->
+      let l' = mapi f l in
+      let r' = mapi f r in
+      let v' = f k v in
+      if l == l' && r == r' && v == v' then s
+      else map_inj (MNode (l', k, v', r', h))
+
+  end
+
+  let smartmap = Smart.map
+  let smartmapi = Smart.mapi
+
   module Unsafe =
   struct
 
diff --git a/clib/cMap.mli b/clib/cMap.mli
index bb0019bb82..b45effb95b 100644
--- a/clib/cMap.mli
+++ b/clib/cMap.mli
@@ -58,14 +58,23 @@ sig
   (** Folding keys in decreasing order. *)
 
   val smartmap : ('a -> 'a) -> 'a t -> 'a t
-  (** As [map] but tries to preserve sharing. *)
+  (** [@@ocaml.deprecated "Same as [Smart.map]"] *)
 
   val smartmapi : (key -> 'a -> 'a) -> 'a t -> 'a t
-  (** As [mapi] but tries to preserve sharing. *)
+  (** [@@ocaml.deprecated "Same as [Smart.mapi]"] *)
 
   val height : 'a t -> int
   (** An indication of the logarithmic size of a map *)
 
+  module Smart :
+  sig
+    val map : ('a -> 'a) -> 'a t -> 'a t
+    (** As [map] but tries to preserve sharing. *)
+
+    val mapi : (key -> 'a -> 'a) -> 'a t -> 'a t
+    (** As [mapi] but tries to preserve sharing. *)
+  end
+
   module Unsafe :
   sig
     val map : (key -> 'a -> key * 'b) -> 'a t -> 'b t
diff --git a/clib/hMap.ml b/clib/hMap.ml
index 37f867c6ba..b2cf474304 100644
--- a/clib/hMap.ml
+++ b/clib/hMap.ml
@@ -383,13 +383,21 @@ struct
     let m = Map.set k x m in
     Int.Map.set h m s
 
-  let smartmap f s =
-    let fs m = Map.smartmap f m in
-    Int.Map.smartmap fs s
+  module Smart =
+  struct
+
+    let map f s =
+      let fs m = Map.Smart.map f m in
+      Int.Map.Smart.map fs s
+
+    let mapi f s =
+      let fs m = Map.Smart.mapi f m in
+      Int.Map.Smart.map fs s
+
+  end
 
-  let smartmapi f s =
-    let fs m = Map.smartmapi f m in
-    Int.Map.smartmap fs s
+  let smartmap = Smart.map
+  let smartmapi = Smart.mapi
 
   let height s = Int.Map.height s
 
diff --git a/clib/option.ml b/clib/option.ml
index 32fe2fc5f5..7a3d5f934f 100644
--- a/clib/option.ml
+++ b/clib/option.ml
@@ -100,12 +100,6 @@ let map f = function
   | Some y -> Some (f y)
   | _ -> None
 
-(** [smartmap f x] does the same as [map f x] except that it tries to share
-    some memory. *)
-let smartmap f = function
-  | Some y as x -> let y' = f y in if y' == y then x else Some y'
-  | _ -> None
-
 (** [fold_left f a x] is [f a y] if [x] is [Some y], and [a] otherwise. *)
 let fold_left f a = function
   | Some y -> f a y
@@ -176,6 +170,21 @@ let lift2 f x y =
   | _,_ -> None
 
 
+(** {6 Smart operations} *)
+
+module Smart =
+struct
+
+  (** [Smart.map f x] does the same as [map f x] except that it tries to share
+      some memory. *)
+  let map f = function
+    | Some y as x -> let y' = f y in if y' == y then x else Some y'
+    | _ -> None
+
+end
+
+let smartmap = Smart.map
+
 (** {6 Operations with Lists} *)
 
 module List =
diff --git a/clib/option.mli b/clib/option.mli
index 14fa9da38f..8f82bf090b 100644
--- a/clib/option.mli
+++ b/clib/option.mli
@@ -75,9 +75,8 @@ val iter2 : ('a -> 'b -> unit) -> 'a option -> 'b option -> unit
 (** [map f x] is [None] if [x] is [None] and [Some (f y)] if [x] is [Some y]. *)
 val map : ('a -> 'b) -> 'a option -> 'b option
 
-(** [smartmap f x] does the same as [map f x] except that it tries to share
-    some memory. *)
 val smartmap : ('a -> 'a) -> 'a option -> 'a option
+[@@ocaml.deprecated "Same as [Smart.map]"]
 
 (** [fold_left f a x] is [f a y] if [x] is [Some y], and [a] otherwise. *)
 val fold_left : ('b -> 'a -> 'b) -> 'b -> 'a option -> 'b
@@ -123,6 +122,16 @@ val lift_left : ('a -> 'b -> 'c) -> 'a option -> 'b -> 'c option
     [Some w]. It is [None] otherwise. *)
 val lift2 : ('a -> 'b -> 'c) -> 'a option -> 'b option -> 'c option
 
+(** {6 Smart operations} *)
+
+module Smart :
+sig
+
+  (** [Smart.map f x] does the same as [map f x] except that it tries to share
+      some memory. *)
+  val map : ('a -> 'a) -> 'a option -> 'a option
+
+end
 
 (** {6 Operations with Lists} *)