String Trie in OCaml

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?

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.

StackExchange Code Review Q#10154, answer score: 3