Ocaml TRIE 实现

Question

我正在尝试将这个 trie 实现用于 ocaml:http://www.lri.fr/~filliatr/ftp/ocaml/ds/trie.ml.html

这是我对模块“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;;

忽略不正确的语义(相等、比较等)。

我使用的是 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 实现不需要的字段(标签、中缀等)。

Answer 1

您必须在顶层之前输入过类似 open Batteries;; 的内容。因此，trie.ml 中的 module Make (M : Map.S) = struct 被解释为定义签名 Batteries 参数的仿函数 Make。 map .S.

现在，Batteries.Map.S 包含标准 Map.S 的所有类型、方法……，因此您不会注意到这个问题#using trie.ml，仅在稍后尝试应用 Make 时使用。但 Jean-Christophe Filliâtre 在编写文件时打算使用标准 Map.S。如果您编译了 trie.ml 而不是 #using 它，Map.S 将被解析为标准库的。编译和#loading trie.ml 的另一个优点是创建 trie 模块的仿函数将被命名为 Trie.Make(同样，正如 Jean-Christophe 的意图:Make alone 是不明确的，仅在另一个提供上下文的模块中按约定使用:Hashtbl.Make、Set.Make、...)