****.mli file**
type ('k, 'v) trie
val empty : ('k, 'v) trie
val insert : ('k, 'v) trie -> 'k list -> 'v -> ('k, 'v) trie
****.ml file**
type ('k, 'v) trie = Trie of 'v option * (('k * ('k, 'v) trie) list)
(** The empty trie *)
let empty = Trie (None, [])
let rec insert t ks v =
let (key, subtries) = t in
match ks with
|[] -> Trie (Some v, subtries)
|k::krest -> (if (List.fold_left (equal_to k) false (List.map pair2key subtries)) then
(* current k was pointing to one of the current subtries -- update it from now on *)
(* Trie (key, subtries) *)
(* Trie (key, (List.map (fun (k,st) -> (k,st)) subtries)) *)
Trie (key, (List.map (fun (k,st) -> (k,(insert st krest v))) subtries))
else
(* current k was not in this level -- make a new trie to continue *)
Trie (key, subtries @ [k, (insert empty krest v)])
)
***************************
the error:
***************************
File "trie.ml", line 23, characters 73-81:
Error: This expression has type ('a * ('a, 'b) trie) list
but an expression was expected of type
('c * ('b option * ('a * ('a, 'b) trie) list)) list