gistfile1.ml

module CMap = Map.Make(struct
  type t = char
  let compare = Char.compare
end)

type t = Trie of (t CMap.t * bool)

let empty = Trie (CMap.empty, false)

let add word trie =
  let rec loop i (Trie (m, eow)) =
    if i = String.length word then
      Trie (m, true)
    else
      try
        let trie' = CMap.find word.[i] m in
        Trie (CMap.add word.[i] (loop (i+1) trie') m, eow)
      with Not_found ->
        Trie (CMap.add word.[i] (loop (i+1) empty) m, eow)
  in
  loop 0 trie


let rec mem word trie =
  let rec loop i (Trie (m, eow)) =
    if i = String.length word then
      eow
    else
      try
        let trie' = CMap.find word.[i] m in
        loop (i+1) trie'
      with Not_found ->
        false
  in

  loop 0 trie