3
我試圖使用ocaml的這個線索的實現：http://www.lri.fr/~filliatr/ftp/ocaml/ds/trie.ml.htmlocaml的TRIE實施
這是我實現的模塊 「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的實現（標籤，中綴等）所不需要的字段。