trie_insert.ml

let rec insert (s: char list) (trie: trie) : trie =
  let Node(children, hasEntry) = trie in match s with
    | [] -> Node(children, true)
    | first_char :: rest ->
      let currentChild = if ChildList.mem first_char children
        then (ChildList.find first_char children)
        else empty
      in
      let newChild = insert rest currentChild in
      let newChildren = ChildList.add first_char newChild children in
      Node(
        newChildren,
        hasEntry
      )
;;