在 Ocaml 中打印一个 trie

Question

下面列出的每个函数都按预期工作。（除了最后一个）

我正在尝试让 to_list 工作，我希望它成为 return list of char lists，但到目前为止我只设法实现了它与简单的 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 []

编辑：感谢@Goswin von Brederlow 我使我的 to_list 打印功能更清晰。

我尝试了什么：

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

示例：

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

它失败是因为 List.map 可以 return 只键入 'a list 而不是任何 n-depth nested lists 吗？

Answer 1

List.map可以return一个列表列表。这不是你的问题。

你说你的 to_list 函数没有编译，但你没有显示错误。这使得提供建议变得更加困难。

我在代码中看到的第一个问题是：

List.map (fun (c, t) -> to_list' (c::acc) t)

这里只有一个参数。但通常你会想要提供两个参数：一个函数（你有）和一个列表（你没有）。

Answer 2

有两种合理的方法可以做到这一点：让 map return 一个列表列表然后将其展平，或者对累加器进行线程化。我会给出第二个，因为它更有效并且不会更复杂：

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

在 Ocaml 中打印一个 trie

Print a trie in Ocaml

ocaml

functional-programming

trie

nested-lists