String Trie in OCaml

Question

I'm pretty new to OCaml, so any feedback is appreciated. The goal is to implement a trie that efficiently stores and sorts strings.

module CharMap = Map.Make(Char)
(* count of members of the set that end at this node * mapping from
 next char => children *)
type trie = Node of int * trie CharMap.t
let empty = Node (0, CharMap.empty)
(* Add a string to the trie *)
let rec add (Node (count, children) : trie) = function 
 | "" -> Node (count + 1, children)
 | str -> 
 let firstChar = String.get str 0 in
 let lastChars = String.sub str 1 ((String.length str) - 1) in
 let newTrie = if CharMap.mem firstChar children
 then add (CharMap.find firstChar children) lastChars
 else add empty lastChars in
 let newChildren = CharMap.add firstChar newTrie children in 
 Node (count, newChildren)
let addAll (trie : trie) (strs : string list) : trie =
 List.fold_left (fun trieAcc str -> add trieAcc str) empty strs 
(* Get all the strings of a trie *)
let traverse (trie : trie) : string list =
 let rec helper (Node (count, children) : trie) (prevChar : char option)
 : string list =
 let string_of_char chr = 
 match chr with 
 | None -> ""
 | Some ch -> String.make 1 ch in
 let perChild = List.map (fun (chr, child) -> 
 (helper child (Some chr))) (CharMap.bindings children) in
 let fromChildren = List.flatten perChild in
 let withPrev =
 List.map (fun str -> (string_of_char prevChar) ^ str) fromChildren in
 let rec clone str count = 
 if count = 0 then [] else str::(clone str (count - 1))
 in (clone (string_of_char prevChar) count) @ withPrev in 
 helper trie None
let sort (strs: string list): string list =
 traverse (addAll empty strs)

What do you think?

Answer 1

You're pretty new to OCaml? You're using OCaml 3.12 features and probably did a lot of functional programming before. Let's see if I can show what idioms I've seen before. I'm not an OCaml expert though, far from it.

Empty trie Consider using something like Empty to denote the empty trie. type trie = Empty | Node of int * trie CharMap.t This is better than your empty hack, and will allow you to take advantage of OCaml's pattern matching.

string_of_char is a nice OCaml name, but this is not really string_of_char, but string_of_char_option. Since it's not important, I'd tend to make it look smaller in the code.

let string_of_char_option = function None -> "" | Some ch -> String.make 1 ch

Auxiliary function name You don't need to use the name helper: traverse is fine. It's not ambiguous since traverse is not recursive. This applies to all functions with auxiliary functions.

Indentation I'm not sure I understand how you choose to put your ins. Also, fromChildren has a wrong indentation.

• Nick Heiner: Thanks for the feedback! Good catch on string_of_char. I feel like string_of_char_opt is a good compromise. I know it's not ambiguous, but shadowing variables from enclosing scopes (like having traverse within traverse) feels too "clever". Indentation is weird, I know. I'm trying to keep it as readable as possible with 80 chars/line.
• Nick Heiner: I'm not sure about Empty. Adding Empty to type trie means that there are now more ways to encode emptiness, increasing complexity. Also, there's never a time that I check if some trie = empty, so it's not clear when I'd take advantage of the pattern matching.

Answer 2

This is how I would write the traverse function:

(* Get all the strings of a trie *)
let traverse (trie : trie) : string list =
 let string_of_char chr = String.make 1 chr in
 let rec traverse (Node (count, children) : trie) (prevString : string) : string list =
 let fromChildren = List.flatten (List.map (fun (chr, child) -> 
 (traverse child (prevString^(string_of_char chr)))) (CharMap.bindings children))
 in
 let rec clone count =
 if count = 0 then fromChildren
 else prevString::(clone (count - 1))
 in
 clone count
 in
 traverse trie ""

I think you use too much auxiliary variables, there is no need for them here.

The next step when you have a fonction like this is to use minimum space on the stack, for that you must remove the List.flatten function:

let traverse_tr trie =
 let string_of_char chr = String.make 1 chr in
 let rec traverse (Node(count, children)) prevString acc =
 let rec clone count acc =
 if count = 0 then acc
 else (clone (count-1) (prevString :: acc))
 in
 CharMap.fold (fun chr t -> traverse t (prevString^(string_of_char chr)) )
 children (clone count acc)
 in
 traverse trie "" []