3

私はデータ型trie=文字のノード*（trie ref）リストを持っています| 空そして私はこれらの2つの相互再帰関数を使用して、トライ内のすべての単語を収集したいと思います。

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)

私は何年もの間これに固執してきました、私はどんな助けにも感謝します。

4

1 に答える 1

2

継続への入力は単語の接尾辞であるため、次の継続が呼び出された後、結果はトライ内の単語のリストに近くなり、それでも単語の接尾辞である必要があります。これを使用して、継続が行うことになっていることは、トライの次の文字を付加することであると判断できます（charリストリストが与えられた場合、リスト内のすべてのcharリストにcharが付加されます）。

fun words_in_trie Empty cont = cont[]

渡すトライがである場合、そのトライにEmptyは1つの単語があり、それは空の文字列です。必要な結果はです[""]。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関数は私にはうまく見えます。

于 2012-02-26T07:18:05.773 に答える