SML - сбор слов в дереве с использованием продолжений - PullRequest
Новая
       36

SML - сбор слов в дереве с использованием продолжений

3 голосов
/ 25 февраля 2012

У меня есть тип данных Trie = Node of char * (Trie Ref) список |Пусто И я хочу собрать все слова в дереве, используя эти две взаимно рекурсивные функции: 

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

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

и затем вызывая их с удовольствием. 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)

Я застрял на этом целую вечность, я буду признателен за любую помощь.

1 Ответ

2 голосов
/ 26 февраля 2012

Поскольку входные данные для продолжения являются постфиксом слов, вы знаете, что после вызова следующего продолжения результат должен быть ближе к списку слов в дереве и все же быть постфиксом слов. Вы можете использовать это, чтобы определить, что продолжение должно предполагать добавление следующей буквы вверх по дереву (с учетом списка списков символов, оно будет добавлять символ к каждому списку символов в списке). 

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, к которому вы хотите применить продолжение (которое добавляет все символы в цепочку). Вы должны создать продолжение так, чтобы в дополнение к добавлению всех символов из узлов вверх по дереву, оно также добавляло char c от текущего узла. То, что вы ищете, выглядит примерно так: 

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

Приведенное выше добавляет c к каждому char list в списке, затем передает его следующему продолжению, которое продолжается до следующего char.

Ваша all_words функция выглядит хорошо для меня.

...