Mer OCaml

This one was quite tricky, and my solution is inelegant, but I’m glad to have gotten it.

Inserting a new word into the trie (data structure as defined earlier):

let rec insert word =
  let first = String.get word 0
  and rest = String.sub word 1 (String.length word - 1)
  in let insert_node = function
    Letter(c,b,nl) as l -> if (first=c) then
                             if (String.length rest)=0 then Letter(c,true,nl)
                             else Letter(c,b,insert rest nl)
                           else l
     in function
         (Letter(c,_,_) as h)::t when (first=c) -> (insert_node h)::t
       | h::t                                   -> h::(insert word t)
       | []                                     -> [insert_node (Letter(first,false,[]))];;

Some helpers for free:

let rec string_of_trie trie =
  let string_of_node = function
    Letter(c,b,nl) -> (String.make 1 c) ^ (if b then "*" else "") ^ " " ^ (string_of_trie nl)
  in "[" ^ (String.concat "; " (List.map string_of_node trie)) ^ "]";;

let print_trie trie =
  print_endline (string_of_trie trie);;

Next I think I have to establish the height of this thing or something, so that’ll let me do a prettier print_trie later.

Style comparison:

let rec construct = function
    []   -> []
  | h::t -> insert h (construct t);;

let construct wl =
  List.fold_left (fun x y -> insert y x) [] wl;;