SML - 使用continuation收集trie中的單詞

Question

我有一個 數據類型trie = Node * char *（trie ref）list |空 我想收集線索的所有單詞，使用這兩個相互遞歸函數：

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

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

，然後用 樂趣all_entries T = all_words噸（FN L電話他們=>地圖（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

由於連續輸入是單詞的後綴，因此您知道在調用下一個連續之後，結果必須更接近trie中的單詞列表，並且仍然是單詞的後綴。你可以使用它來確定繼續應該做什麼是在trie之前加上下一個字母（給定一個char列表，​​它會在列表中的每個char列表前加一個char）。

fun words_in_trie Empty cont = cont[] 

如果你傳遞線索是Empty，那麼你必須在特里一個詞，那就是一個空字符串。你想要的結果是[""]。回想一下，上一次繼續將列表中的每個char list轉換爲string，因此爲了獲得該結果，需要將它傳遞給一個空列表char list的列表進行轉換。

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

回想一下：繼續的類型是char list list -> 'a。 c是char，因此它不能被預置爲r，其類型爲char list list。

all_words返回您想要應用延續的嘗試列表rl中包含的所有單詞的列表（它將前導字符串中的所有字符前導）。您必須構建延續，以便除了從節點上的所有字符開始預先加上字符串外，還要預加當前節點的charc。什麼是你正在尋找的東西是這樣的：

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

上述預規劃c到列表中的每個char list，然後將其傳遞到下一個延續，它接着前面加上下一char。

您的all_words功能對我來說很好。