在 OCaml 中创建 char Trie

Question

我正在尝试在 OCaml 中构建初始 Trie 结构，其中边缘是字符。所以字符串 "ESK" 将被映射为：

[('E', [('S', [('K', [])])])]

我对此的定义是：

type trie = Trie of (char * trie) list

然而，在实现 add 函数时：

 let rec add_string str =
    let key = String.get str 0 in
    if String.length str = 1 then
      (key, empty_trie) :: []
    else
      (key, add_string (tail str)) :: []

对于 add (tail str) 编译器给我：

Error: This expression has type (char * trie) list
       but an expression was expected of type trie

我对此有点困惑，因为我没有将 trie 定义为 (char * trie) list?

tail 就是 let tail str = String.slice str 1 (String.length str) 而 empty_trie 就是 let empty_trie = Trie([])

Answer 1

已解决。 Trie 应明确使用：

let rec add_string str =
  let key = String.get str 0 in
  if String.length str = 1 then
    (key, empty_trie) :: []
  else
    (key, Trie (add_string (tail str))) :: []

这将导致 add_string "ESK" 产生：

(char * trie) list = [('E', Trie [('S', Trie [('K', Trie [])])])]

Answer 2

请注意，更惯用的函数编写方式是

let rec add_string str =
  let key = str.[0] in
  if String.length str = 1 then
    Trie [key, empty_trie]
  else
    Trie [key, add_string (tail str)]

那么add_string还有两个问题：首先它在每次迭代时重新分配一个新的字符串。跟踪当前位置更简单高效：

let add_string str =
  let rec add_string_aux pos str =
    if pos = String.length str then empty_trie
    else
      let key = str.[pos] in
      Trie [key, add_string_aux (pos+1) str] in
  add_string_aux 0 str

第二个问题是该函数的名称不正确，因为它不会将字符串添加到现有的 trie 中，而是从字符串构建 trie：from_string 或 of_string 可能是更好的名称.

在 OCaml 中创建 char Trie

Creating char Trie in OCaml

ocaml

functional-programming

variant