5
\$\begingroup\$

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?

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$ – Nick Heiner Mar 19 '12 at 23:04
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Nick Heiner Mar 19 '12 at 23:06
2
\$\begingroup\$

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 "" []
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.