****.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