Trie data structure in OCaml

Question

I am trying to build a trie in OCaml:

type ('a, 'b) trie = Nil | Cons of 'a * 'b option * ('a, 'b) trie list;;

(* find place to insert key in a list of tries *)
let rec findInsert key x  =
    match x with
    [] -> Nil
    | x::xs -> let Cons(k, _, _) = x in 
        if key = k then x else findInsert key xs;;

(* inser pair in a trie *)
let rec insert ( key, value ) trie =
    match trie with
    Nil -> Cons(key, value, [])
    | t -> let Cons(k, v, trieList) = t and
        subTree = insert (key, value) (findInsert key trieList) and
        newSubTree = subTree::trieList in
        Cons(k, v, newSubTree);;

But this gives me the following error:

val findInsert : 'a -> ('a, 'b) trie list -> ('a, 'b) trie = <fun>
File "trie.ml", line 15, characters 54-62:
Error: Unbound value trieList

EDIT:: Thanks to Virgile I now have the a program that compiles:

(* insert pair in a trie *)
let rec insert ( key, value ) trie =
    match trie with
    Nil -> Cons(key, value, [])
    | t -> 
        let Cons(k, v, trieList) = t in
            let subTree = insert (key, value) (findInsert key trieList) in
            Cons(k, v, subTree::trieList);;

But when I try to run it I get this:

# let t  = Cons(3, Some 4, []);;
val t : (int, int) trie = Cons (3, Some 4, [])
# insert (4, Some 5) t;;
Error: This expression has type (int, int) trie/1017
   but an expression was expected of type (int, int) trie/1260

What do those numbers represent?

Answer 1

You shouldn't use let x = ... and y = ... in when y depends on x, as all identifiers bound by the unique let are supposed to be defined at the same time. Use let x = ... in let y = ... in instead, to ensure that x will be in scope when defining y. In your case, this becomes:

let Cons(k, v, trieList) = t in
let subTree = insert (key, value) (findInsert key trieList) in ...