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
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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.