3

I have a datatype trie = Node of char * (trie ref) list | Empty And I want to collect all the words in the trie, using these two mutually recursive functions:

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

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

and then calling them with fun all_entries t = all_words t (fn l => map (fn w => String.implode w) l);

This has to be done with continuations. I've written it in non-continuation form, as follows:

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)

But I can't figure out how to convert them into continuation form! This is what I have so far, but it doesn't work:

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)

I've been stuck on this for ages, I will appreciate any help.

Gilles 'SO- stop being evil'
  • 104,111
  • 38
  • 209
  • 254
Lanaru
  • 9,421
  • 7
  • 38
  • 64
  • Standard ML *per se* doesn't have continuations. Are you using [Standard ML of New Jersey's `SMLofNJ.Cont` structure](http://www.smlnj.org/doc/SMLofNJ/pages/cont.html), or a similar module from elsewhere, or something home-rolled? – ruakh Feb 25 '12 at 16:01
  • Using a continuation that is a function (char list list -> 'a) which takes as input a list of lists denoting the postfix of words it has collected so far – Lanaru Feb 25 '12 at 16:11

1 Answers1

2

Since the inputs to the continuation are the postfix of words, you know that after the next continuation is called, the result has to be closer to the list of words in the trie and still be the postfix of the words. You can use this to determine that what the continuation is supposed to do is prepend the next letter up the trie (given a char list list, it'll prepend a char to every char list in the list).

fun words_in_trie Empty cont = cont[]

If the trie you're passing is Empty, then you have one word in that trie, and that's an empty string. The result you want is [""]. Recall that the last continuation converts every char list in the list to a string, so in order to get that result, you need to pass it a list with an empty char list for it to convert.

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

Recall: the type of the continuation is char list list -> 'a. c is a char, so it can't be prepended to r, which is of type char list list.

all_words returns a list of all words contained in the list of tries rl, to which you want to apply the continuation (which prepends all chars up the trie). You have to build up the continuation so that in addition to prepending all chars from the nodes up the trie, it also prepends the char c from the current node. What you're looking for is something like this:

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

The above prepends c to every char list in the list, then passes it on to the next continuation, which goes on to prepend the next char.

Your all_words function looks fine to me.

howard
  • 644
  • 2
  • 7
  • 15