Print a trie in Ocaml

Question

Every function listed below works as expected. (except the last one)

I'm trying to make the to_list work, I want it to return a list of char lists, but I so far I managed only to implement it with simple prints returning unit

type trie = Trie of bool * (char * trie) list
let empty = Trie (false, [])

let explode wd = (*breaks up a word in a list of chars*)
    let rec exp i acc =
        if i = -1 then acc else exp (i-1) (wd.[i]::acc) in 
        exp (String.length wd - 1) []

let insert tr wd = (*insert a word into the trie*)
let rec insert' wd tr = match wd, tr with 
    | [], Trie (_, l) -> Trie (true, l)
    | wh::wt, Trie (b, l) ->
        try Trie(b, (wh, insert' wt (List.assoc wh l))::List.remove_assoc wh l)
        with Not_found -> Trie (b, (wh, insert' wt empty) :: l)
        in insert' (explode wd) tr

let from_list = List.fold_left insert empty  (*makes trie from string list*)

let to_list tr = (*prints all trie words*)
    let rec to_list' (Trie (b, l)) acc = 
        if b then
            (
                List.iter print_char (List.rev acc); 
                print_char '\n'
            )
        else ();
        List.iter (fun (c, t) -> to_list' t (c::acc)) l in
    to_list' tr []

EDIT : Thanks to @Goswin von Brederlow I made my to_list printing function clearer.

What I tried :

let to_list tr = (*fails at compile time*)
    let rec to_list' acc = function
        | Trie(_, []) -> [List.rev acc]
        | Trie(true, (c, h)::_) -> (List.rev acc) :: to_list' (c::acc) h
        | Trie(_, l) -> List.map (fun (c, t) -> to_list' (c::acc) t) in
        to_list' [] a tr

Example :

let t = from_list ["hello"; "hell"; "helsinki"; "here"];;
# to_list t;;
here
helsinki
hell
hello
- : unit = ()

Does it fail because List.map can return only type 'a list and not any n-depth nested lists ?

Answer 1

There's two reasonable ways of doing this: to have map return a list of lists and then flatten it, or to thread an accumulator. I'll give the second, since it is more efficient and not much more complicated:

let to_list trie =
  let rec recur acc chars (Trie (word_here, entries)) =
    let acc =
      match entries with
      | [] -> acc
      | _ ->
        List.fold_left (fun acc (char, trie) ->
            recur acc (char::chars) trie)
          acc entries in
    if word_here then List.rev chars::acc
    else acc in
  recur [] [] trie