Ocaml count trie元素

Question

我在试着找出我的Trie中有多少个字符。

这是我的Trie类型。

type 'a t = Node of 'a list * ('a arc list) and 'a arc = char * 'a t

这是我的实现，但不是详尽的：

let arc_size trie =
let rec count_arcs counter trie =
match trie with
| Node (_,[]) -> counter
| Node (_,[(_,x)] -> count_arcs (counter+1) trie
in
count_arcs 0 trie;;

如果trie只包含1个单词，这将会起作用。问题是如果trie分支，并且其中一个节点具有此类型的Node(_,[(_,x)] :: _ :: _)

我似乎找不到这种情况下的匹配模式，因为如果我将trie与Node(_，x)进行匹配，那么本例中的x是a arc list，但我的函数有一个trie作为参数。我在扩展到'a arc list中的另一个'a arcs时遇到了麻烦。

Answer 1

您应该在节点的每个子圆弧上递归调用count_arcs函数(您在递归期间保持不变的相同trie上递归调用它，因此如果您的函数命中示例的第二个分支，它将永远不会终止)。

可以依靠List.fold_left，对于具有弧列表的节点x，xs将弧数定义为xs中每个弧的弧数加上x的弧数之和。

或者，您可以使用模式匹配并手动解构弧线列表，但最好将复杂任务拆分成较小的子任务，然后将它们组合起来。如果不允许使用标准库中的函数(用于教学目的)，那么现在是实现您自己的fold函数的好时机。