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).
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, ...)