recursion - SML - 使用延续在 trie 中收集单词

Question

我有一个 数据类型 trie = char * (trie ref) 列表的节点 |空的我想收集 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)

多年来我一直坚持这一点，我将不胜感激任何帮助。

Answer 1

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

fun words_in_trie Empty cont = cont[]

如果您传递的 trie 是 Empty，那么您在该 trie 中有一个词，它是一个空字符串。您想要的结果是 [""]。回想一下，最后一个延续将列表中的每个 char list 转换为 string，因此为了获得该结果，您需要向其传递一个包含空 的列表>char list 用于转换。

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

回想一下:continuation 的类型是 char list list -> 'a。 c 是一个char，所以它不能放在r 之前，r 是char list list 类型.

all_words 返回包含在 rl 列表中的所有单词的列表，您要对其应用延续(将所有字符添加到 trie 中)。您必须构建延续，以便除了在 trie 中的节点中添加所有字符之外，它还会在当前节点中添加 char c。您正在寻找的是这样的东西:

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

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

我觉得你的 all_words 函数没问题。