Ocaml TRIE implementation

Question

I'm trying to use this trie implementation for ocaml: http://www.lri.fr/~filliatr/ftp/ocaml/ds/trie.ml.html

This is my implementation of module "M":

module M =
    struct     
    type key = int
    type 'a t = (int * 'a) list
    let empty = []
    let equal x y = false
    let compare f x y = 1

    let find x l = 
        let pred e = fst e == x in
        let z = List.find pred l in
        snd z

    let add x t m = (x,t)::m

    let remove x m = filter (fun e -> fst e != x) m

    let map f m = 
        let aux (x,y) = (x, f y) in
        List.map aux m

    let mapi f m =
        let aux i (x,y) = (x, f i y) in
        List.mapi aux m

    let mem x m = 
        let l = List.map snd m in
        List.mem x l

    let iter f m =
        let aux x = f (snd x) in
        List.iter aux m

    let fold f m acc1 =
        let aux acc x = f acc (snd x) in
        List.fold_left aux acc1 m               

    let is_empty m = m == empty

end;;

Ignore incorrect semantics (equal, compare, etc).

I'm using ocaml batteries, and this is how I try to make this work:

# #use "trie.ml";;
module Make :
  functor (M : Batteries.Map.S) ->
    sig
      type key = list M.key;
      type t 'a = [ Node of option 'a and M.t (t 'a) ];
      value empty : t 'a;
      value find : list M.key -> t 'a -> 'a;
      value mem : list M.key -> t 'a -> bool;
      value add : list M.key -> 'a -> t 'a -> t 'a;
      value remove : list M.key -> t 'a -> t 'a;
      value map : ('a -> 'b) -> t 'a -> t 'b;
      value mapi : (list M.key -> 'a -> 'b) -> t 'a -> t 'b;
      value iter : (list M.key -> 'a -> 'b) -> t 'a -> unit;
      value fold : (list M.key -> 'a -> 'b -> 'b) -> t 'a -> 'b -> 'b;
      value compare : ('a -> 'a -> int) -> t 'a -> t 'a -> int;
      value equal : ('a -> 'a -> bool) -> t 'a -> t 'a -> bool;
      value is_empty : t 'a -> bool;
    end
# #use "m.ml";;
module M :
  sig
    type key = int;
    type t 'a = list (int * 'a);
    value empty : list 'a;
    value equal : 'a -> 'b -> bool;
    value compare : 'a -> 'b -> 'c -> int;
    value find : 'a -> list ('a * 'b) -> 'b;
    value add : 'a -> 'b -> list ('a * 'b) -> list ('a * 'b);
    value remove : 'a -> BatEnum.t ('a * 'b) -> BatEnum.t ('a * 'b);
    value map : ('a -> 'b) -> list ('c * 'a) -> list ('c * 'b);
    value mapi : (int -> 'a -> 'b) -> list ('c * 'a) -> list ('c * 'b);
    value mem : 'a -> list ('b * 'a) -> bool;
    value iter : ('a -> unit) -> list ('b * 'a) -> unit;
    value fold : ('a -> 'b -> 'a) -> list ('c * 'b) -> 'a -> 'a;
    value is_empty : list 'a -> bool;
  end

# module X = Make(M);;
Error: Signature mismatch:
       Modules do not match:
         sig
           type key = int;
           type t 'a = list (int * 'a);
           value empty : list 'a;
           value equal : 'a -> 'b -> bool;
           value compare : 'a -> 'b -> 'c -> int;
           value find : 'a -> list ('a * 'b) -> 'b;
           value add : 'a -> 'b -> list ('a * 'b) -> list ('a * 'b);
           value remove : 'a -> BatEnum.t ('a * 'b) -> BatEnum.t ('a * 'b);
           value map : ('a -> 'b) -> list ('c * 'a) -> list ('c * 'b);
           value mapi : (int -> 'a -> 'b) -> list ('c * 'a) -> list ('c * 'b);
           value mem : 'a -> list ('b * 'a) -> bool;
           value iter : ('a -> unit) -> list ('b * 'a) -> unit;
           value fold : ('a -> 'b -> 'a) -> list ('c * 'b) -> 'a -> 'a;
           value is_empty : list 'a -> bool;
         end
       is not included in
         Batteries.Map.S
       The field `Labels' is required but not provided
       The field `Infix' is required but not provided
       The field `Exceptionless' is required but not provided
       The field `print' is required but not provided
       The field `of_enum' is required but not provided
       The field `backwards' is required but not provided
       The field `enum' is required but not provided
       The field `choose' is required but not provided
       The field `max_binding' is required but not provided
       The field `min_binding' is required but not provided
       The field `values' is required but not provided
       The field `keys' is required but not provided
       The field `filter_map' is required but not provided
       The field `filteri' is required but not provided
       The field `filter' is required but not provided
       The field `modify' is required but not provided
# 

I don't understand this error. It seems to me that types of methods in my implementation of module "M" are valid.

I also don't understand why ocaml wants fields not required by TRIE's implementation (Labels, infix, etc).

Answer 1

You must have typed something like open Batteries;; earlier in your toplevel. Because of this, module Make (M : Map.S) = struct in trie.ml is interpreted as defining a functor Make of an argument of signature Batteries.Map.S.

Now, Batteries.Map.S contains all the types, methods, ... of the standard Map.S, so you don't notice the issue when #using trie.ml, only later when you try to apply Make. But Jean-Christophe Filliâtre intended the standard Map.S when he wrote his file. If you had compiled trie.ml instead of #using it, Map.S would have been resolved to the standard library's. Another advantage of compiling and #loading trie.ml would be that the functor to create a trie module would be named Trie.Make (again, as intended by Jean-Christophe: Make alone is ambiguous and is only used by convention inside another module that gives the context: Hashtbl.Make, Set.Make, ...)