3

我有一个数据类型 trie = char 的节点 * (trie ref) list | Empty 我想收集 trie 中的所有单词，使用这两个相互递归的函数：

words_in_trie: trie -> (char list list -> 'a) -> 'a

all_words: trie ref list -> (char list list -> 'a) -> 'a

然后用 fun all_entries t = all_words t (fn l => map (fn w => String.implode w) l) 调用它们；

这必须通过延续来完成。我以非延续形式写了它，如下所示：

fun wt Empty = [[]] 
    |wt (Node(c,rl)) = map (fn (l) => c::l) (aw rl)
and aw [] = []
    |aw [h] = wt (!h)
    |aw (h::t) = (wt (!h))@(aw t)

但我不知道如何将它们转换为延续形式！这是我到目前为止所拥有的，但它不起作用：

fun words_in_trie Empty cont = cont[] 
    |words_in_trie (Node(c,rl)) cont = (all_words rl (fn r=> cont(c::r)))
and all_words [h] cont = words_in_trie (!h) cont
    |all_words (h::t) cont = (words_in_trie (!h) cont)@(all_words t cont)

我已经坚持了很长时间，我将不胜感激。

4

1 回答 1

2

由于延续的输入是单词的后缀，你知道在调用下一个延续之后，结果必须更接近于 trie 中的单词列表，并且仍然是单词的后缀。您可以使用它来确定延续应该做的是将下一个字母添加到 trie 之前（给定一个 char 列表列表，它将在列表中的每个 char 列表中添加一个 char）。

fun words_in_trie Empty cont = cont[]

如果您传递的 trie 是Empty，那么您在该 trie 中有一个单词，这是一个空字符串。你想要的结果是[""]。回想一下，最后一个延续将char list列表中的 every 转换为 a string，因此为了获得该结果，您需要将一个带有空的列表传递char list给它以进行转换。

|words_in_trie (Node(c,rl)) cont = (all_words rl (fn r=> cont(c::r)))

回想一下：延续的类型是char list list -> 'a。c是 a char，所以它不能被添加到r类型 的前面char list list。

all_words返回包含在该列表中的所有单词的列表rl，您希望对其应用延续（将所有字符添加到 trie 前面）。您必须建立延续，以便除了将节点中的所有字符添加到 trie 之前，它还添加char c了当前节点的 char。你正在寻找的是这样的：

fn x => cont (map (fn y => c::y) x)

上面c添加到列表中的每个char list，然后将其传递给下一个延续，它继续添加到下一个char。

你的all_words功能对我来说很好。

于 2012-02-26T07:18:05.773 回答