types - 无法理解 OCaml trie 类型声明

Question

我想了解人们如何在 OCaml 中编写 trie。我在网上找到了一个例子:

它定义了一个 map :

module CharMap = Map.Make(Char)

然后它定义了trie的类型:

(* count of members of the set that end at this node * mapping from
     next char => children *)
type trie = Node of int * trie CharMap.t

这是我的问题:trie CharMap.t 是什么？我假设它是某种 map ，但我不知道它是什么。

谢谢

Answer 1

扩展 rgrinberg 的回答:在 OCaml 中，类型构造函数位于其参数之后。所以你有 int list，这是一个整数列表。这里有一个类型构造函数 CharMap.t，它构造键为 char 类型的映射。所以 int CharMap.t 将是从 char 到 int 的映射。 trie CharMap.t 的含义完全类似，除了可能的事实(正如 rgrinberg 指出的)，这是 trie 类型的递归使用。它类似于树的定义，因为树的节点中包含的东西本身就是树。在这里，trie 中包含的东西本身就是 trie。