Ocaml TRIE реализация

Question

Я пытаюсь использовать эту реализацию Trie для ocaml: http://www.lri.fr/~filliatr/ftp/ocaml/ds/trie.ml.html

Это моя реализация модуля "М":

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;;

Игнорировать неверную семантику (равно, сравнивать и т. Д.).

Я использую батареи ocaml, и вот как я пытаюсь заставить эту работу:

# #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
# 

Я не понимаю эту ошибку. Мне кажется, что типы методов в моей реализации модуля "M" являются действительными.

Я также не понимаю, почему ocaml хочет поля, не требуемые реализацией TRIE (Labels, infix и т. Д.).

Answer 1

Вы должны были напечатать что-то вроде open Batteries;; раньше на вашем верхнем уровне. Из-за этого, module Make (M : Map.S) = struct в trie.ml интерпретируется как определение функтора Make аргумента подписи Batteries.Map.S,

Сейчас, Batteries.Map.S содержит все типы, методы,... стандарта Map.S, поэтому вы не замечаете проблему при использовании #using trie.ml, только позже, когда вы пытаетесь применить Make, Но Жан-Кристоф Филлиатр намеревался стандарт Map.S когда он написал свое дело. Если вы скомпилировали trie.ml вместо #using его, Map.S был бы разрешен в стандартной библиотеке. Еще одно преимущество компиляции и #loading trie.ml заключается в том, что функтору для создания модуля trie будет присвоено имя Trie.Make (опять же, как и предполагал Жан-Кристоф: Make одни неоднозначно и используется только по соглашению внутри другого модуля, который дает контекст: Hashtbl.Make, Set.Make...)