Insert implementation for a trie in Ocaml

Question

I don't have any idea on how to change the code for my add function.

type trie = Node of bool * (char * trie) list 

let explode word = 
       let rec explode' i acc = 
           if i < 0 then acc else explode' (i-1) (word.[i] :: acc) 
            in explode' (String.length word - 1) []

let rec exists w tr = match w, tr with
    | [], Node (b, _) -> b
    | h::t, Node (_, l) -> try exists t (List.assoc h l) with Not_found -> false

let rec add w tr = match w, tr with 
    | [], Node (_, l) -> Node (true, l)
    | h :: t, Node (b, l) -> try add t (List.assoc h l)   
                             with Not_found -> Node (false, (h, add t tr) :: l)

The problem is when List.assoc h l finds something , then I don't keep track of my structure, no Node is built during the recursive call so I am losing data.

Example :

# let empty = Node(true, []);;
 - : trie = Node (true, [])
# let w = explode "hi";;
val w : char list = ['h'; 'i']
# let ww = explode "hit";;
val ww : char list = ['h'; 'i'; 't']
# let tr = add w x;;
val tr : trie = Node (false, [('h', Node (false, [('i', Node (true, []))]))])
# add ww tr;;
- : trie = Node (false, [('t', Node (true, []))])

Answer 1

It seems your basic plan is to work down through the data structure with List.assoc, then add your new node when you find the right spot. This makes sense if you can modify the structure. However, your data structure is immutable. With immutable data, your basic plan must be to build a new data structure rather than to modify the old one. So you have to imagine yourself finding the right spot while keeping traack of the old structure along the way, then building up a new structure starting from the spot.

Here's some code that keeps an association list counting the number of instances of characters seen so far. Note that it returns a new association list rather than modifying the old one (which is impossible):

 let rec add_char_count list char =
     match list with
     | [] -> [(char, 1)]
     | (hchar, hcount) :: t -> 
         if hchar = char then (hchar, hcount + 1) :: t
         else (hchar, hcount) :: add_char_count t char

The recursive call (hchar, hcount) :: add_char_count t char is the spot where the old structure is remembered. It rebuilds the old structure from the part of the list before where the new character is added.