OCaml Trie Data Structure

Question

I am trying to create 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 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 the following:

 # 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 these numbers represent?

Answer 1

You should not use let x = ... and y = ... in if y depends on x , since all identifiers associated with the unique let must be defined at the same time. Instead, use let x = ... in let y = ... in to ensure that x will be in scope when defining y . In your case, it will be:

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

Answer 2

When using the top level, if you specify the same type twice, ocaml will see two types, not one. Since your two types have the same name trie , they are renamed trie/1017 and trie/1260 . If you recompile a type declaration, you must recompile all other declarations that rely on this type to use the new type, not the old one.

Another note: you should never write

 match foo with | a -> let PATTERN = a in 

you should use this instead:

 match foo with | PATTERN ->