在 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

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

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可能是更好的名称。

Answer 2

已解决。 应明确使用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 [])])])]