Implementation attempt of a trie (http://nullwords.wordpress.com/2013/03/06/the-trie-data-structure-a-prefix-tree-for-autocompletes/)

gistfile1.ml

type t = node list
and node = Node of (char * node list) | Eow

let empty = []


let mem word nodes =
  let len = String.length word in

  (* Return the children nodes of the node containing the character c,
     or None if no node contains c. *)
  let rec find_subnodes nodes c =
    match nodes with
    | [] -> None
    | Eow::nodes' -> find_subnodes nodes' c
    | (Node (d, subnodes))::nodes' ->
        if c = d then
          Some subnodes
        else
          find_subnodes nodes' c
  in

  (* For each i'th character in word, find the node that contains the
     character and recurse down that node with the rest of the word.
     Once all characters have been processed, make sure there's an
     end-of-word marker in the children of the current nodes. *)
  let rec contains nodes i =
    if i = len then
      List.mem Eow nodes
    else
      let c = word.[i] in
      match find_subnodes nodes c with
      | None -> false
      | Some nodes' -> contains nodes' (i+1)
  in

  contains nodes 0


let add word nodes  =
  let len = String.length word in

  (* Create the nodes missing from the trie to add the word. *)
  let rec insert_aux nodes i =
    if i = len then
      [Eow]
    else
      let c = word.[i] in
      match nodes with
      | [] -> [Node(c, insert_aux [] (i+1))]
      | Eow::nodes' -> Eow :: (insert_aux nodes' i)
      | (Node(d, subnodes))::nodes' ->
          if c = d then
            Node(c, insert_aux subnodes (i+1))::nodes'
          else
            Node(d, subnodes) :: (insert_aux nodes' i)
  in

  insert_aux nodes 0