On this page:
1 Prefix Trees
2 Generative Recursion
6.10.1

Assignment 11: Mutual and Generative Recursion

This assignment is due on Wednesday, 11/08 at 11:59 PM. Submit it using the Handin server as assignment a11.

Important Note Whenever we say to "design a function", we mean that you need to follow (and when necessary, adapt) a design recipe. When you write a generative recursive function, you must provide a termination argument.

Important Note Use Intermediate Student with lambda on this assignment, and further assignments in this course.

1 Prefix Trees

When data is organized in an unstructured list and we want to search for an element, in general our only option is to inspect every item until we find what we’re looking for.

Prefix trees are one solution to organizing data in a way that facilitates searching for an element. An example of a prefix tree is all of the entries in a printed dictionary whose headwords start with the same letter. When you are looking for the definition of a word in such a dictionary, it suffices to go letter by letter in alphabetical order.

; A PrefixForest is a [NEListOf PrefixTree]
 
; A PrefixTree is a
; - (make-end)
; - (make-node 1String PrefixForest)
 
(define-struct end [])
(define-struct node [letter forest])

An example of a prefix tree that contains the strings "on", "one", "of", "off", "oft", and "or" is:

(define pt1
 (make-node "o"
            (list (make-node "n" (list
                                   (make-end)
                                   (make-node "e" (list (make-end)))))
                  (make-node "f" (list
                                   (make-end)
                                   (make-node "f" (list (make-end)))
                                   (make-node "t" (list (make-end)))))
                  (make-node "r" (list (make-end))))))

This tree is displayed visually as:

A PrefixForest should never contain multiple nodes with the same letter. You can make this assumption when your code receives a PrefixForest in its input, and you must maintain this guarantee when your code produces a PrefixForest in its output.

We write Word to mean a list of 1Strings.
; a Word is a [ListOf 1String]
Feel free to use explode in your tests to easily convert a string to a Word.

Exercise 1 Define two examples of PrefixTrees and two examples of PrefixForests.

Exercise 2 Design a function alphabetize which sorts all of the nodes in a PrefixForest in alphabetical order according to their letter and which puts all of the ends first. (In other words, for the comparison function, a tree which is an end is less than any node.) alphabetize should also sort the forest associated to any node in the input forest. Feel free to use sort and string comparison functions such as string<?.

Exercise 3 Design functions word-in-tree? and word-in-forest? which determine whether or not a given Word is stored, respectively, in a PrefixTree and in a PrefixForest. Note that the empty word is stored in an end. Moreover, the empty word is the only word stored in an end and can only be stored in an end.

Exercise 4 Design a function word->tree which takes a Word and returns a PrefixTree which stores exactly that word.

Exercise 5 Design functions add-to-tree and add-to-forest.

add-to-tree takes a Word and a PrefixTree and adds the word to the tree, returning a new tree. The given word must be non-empty, and the given tree must be a node whose letter matches the first letter of the given word.

add-to-forest takes a Word and a PrefixForest and adds the word to the forest, returning a new forest.

Exercise 6 Design functions tree->list and forest->list which take a PrefixTree or PrefixForest and returns a [NEListOf String] containing all of the words (as strings this time) stored in the input tree or forest.

Exercise 7 Design a function list->forest which takes a [NEListOf String] and returns a PrefixForest that stores the given words (given as strings this time). Hint: follow the template for processing [NEListOf String] and use explode, word->tree, and add-to-forest.

Extra fun What happens to a [NEListOf String] if you feed it to list->forest, then alphabetize, then forest->list?

2 Generative Recursion

Exercise 8 Book exercise 422

Exercise 9 Book exercise 423

Exercise 10 Design the function tokenize. This function takes a [ListOf 1String] as input, and produces a [ListOf String]. Each string in the result should be a sequence of lower-case letters that were next to each other in the input list, without any other kinds of character or white space in between. Here are some examples:

(check-expect (tokenize (list "a" "b" " " "c" ";" "d" "e"))
              (list "ab" "c" "de"))
(check-expect (tokenize (list " " "-" " " ";" "d" "e"))
              (list "de"))
(check-expect (tokenize (list " " "-" " " ";" "d" "e" "(" ")"))
              (list "de"))
(check-expect (tokenize (list " " "-" " " ";" "#" "+"))
              (list))

Hint: The key part of generative recursion is figuring out what subproblem to solve recursively. Design a helper function to generate the subproblem from the problem. You will find the function string-lower-case? useful.