Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.