public
Created

  • Download Gist
gistfile1.ml
OCaml
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.