Trees & Mutually Recursive Data Definitions

Instructions for students & labbies:

Students use DrScheme, following the design recipe, working on the exercises at their own pace, while labbies wander among the students, answering questions, bringing the more important ones to the lab's attention. Students should feel free to skip the challenge exercises.

Trees

In class, we used ancestor family trees as an example form of trees. In ancestor family trees, each person (a make-child structure) has 0, 1, or 2 ancestors (also make-child structures). Here, we'll use a similar, but slightly different, form of trees for more experience.

In mathematics, we can model arithmetic expressions as trees. For example,

      5+(1-8)×(7+1)

or equivalently, the Scheme code

      (+ 5 (* (- 1 8) (+ 7 1)))

is pictorially

         +
       /   \
      5     ×
          /   \
         -     +
        / \   / \
       1   8 7   1

This tree form has some advantages. To understand the more familiar linear form, you must know about the order of operator precedence, whereas that is unnecessary in the tree form. The tree also eliminates the need for parentheses. The tree also gets us away from the relatively minor concerns of the precise details of mathematical or Scheme notation, like infix vs. prefix operators.

Consider if you were developing a computer program like DrScheme (or, similarly, a "compiler," if you know what that is). Such a program would take the linear form, which is convenient for a person to type in, but then convert or parse it to the tree form for internal use. Since parsing is beyond the scope of this course, let's just skip straight to the tree form.

We'll require that each addition, subtraction, multiplication, and division has exactly two subexpressions. Of course, recursively, each subexpression can be another addition, subtraction, multiplication, or division. As a base case, an expression can also be a number.

      (define-struct add (m n))
      (define-struct sub (m n))
      (define-struct mul (m n))
      (define-struct div (m n))

      ; An Arithmetic-Expression (AExp) is one of
      ; - a number
      ; - (make-add m n)
      ;   where m,n are AExps
      ; - (make-sub m n)
      ;   where m,n are AExps
      ; - (make-mul m n)
      ;   where m,n are AExps
      ; - (make-div m n)
      ;   where m,n are AExps

With this data definition, the above tree is modeled by the structure

      (define AExp1 (make-add 5
                              (make-mul (make-sub 1 8)
                                        (make-add 7 1))))

Another sample AExp is

      (define AExp2 16)

As always, we distinguish between the information (the mathematical expression or its corresponding tree) and its data representation (this AExp). Just writing this piece of data doesn't mean we can do anything with it yet, such as compute the intended result.

Exercise

Make more example data. Develop the function evaluate which takes an AExp as input and returns the number that the expression mathematically computes. For example, (evaluate AExp1) should result in -51, and (evaluate AExp2) should result in 16. Challenge exercise: Let's say we had many basic operations, not just these four. We would want to have one structure for any binary operation, using a separate data definition enumerating all of our operations. Rewrite the data definitions, examples, and evaluate for this. As a further challenge, also allow unary operations.

Files and Directories

The following are data definitions for one possible (simplified) representation of files and directories (a.k.a. folders). Observe the mutual recursion between files and list-of-files.

      (define-struct dir (name contents))

      ; A file is one of
      ;   - a symbol
      ;     representing a "simple" file's name
      ;   - a directory
      ;     (make-dir name contents)
      ;     where name is a symbol, and contents is a l-o-f.

      ; A list-of-files (l-o-f) is one of
      ;   - empty
      ;   - (cons f lofd)
      ;     where f is a file, and lofd is a l-o-f

This is very similar to the descendant trees data structure seen in class. Tree-based data structures are very common!

Directory exercises

Create some sample data for the above types. Write the templates for the above types. Develop a function ; find? : symbol file -> boolean ; Returns whether the filename is anywhere in the ; tree of files represented by the file. This includes both ; simple file names and directory names. Aside Note that this is a vast simplification of find, the mother-of-all everything-but-the-kitchen-sink UNIX directory traversing command. If you're curious, at a UNIX prompt, enter man find to see what it can do. Use DrScheme's stepper to step through an example use of find?. Following the templates leads to an overall strategy known as depth-first search. I.e., it explores each tree branch to the end before moving on to the next branch. Develop the following function: ; any-duplicate-names? : file -> boolean ; Returns whether any (sub)directory directly or indirectly contains ; another directory or file of the same name. It does NOT check ; for duplicated names in separate branches of the tree. There's a straightforward way that just follows the template. Challenge: Develop a program to check for duplicated names among all directories and files in the given tree, not just subdirectories. Here's a hint. Develop the following function: ; flatten-dir-once : symbol file -> (file or l-o-f) ; Returns a structure like the original file, except that any ; (sub)directory with that name is removed and its contents ; moved up one level. Here are two pictorial examples, in both cases removing the directory named to-remove. These illustrate why this function can return either a file or a list of files. Input Output Example 1: foo / | \ bar baz to-remove / \ one two foo / / \ \ bar baz one two Example 2: to-remove / | \ foo bar baz foo bar baz Follow the templates and think about a single case at a time. If you do that, it shouldn't be too difficult. If you don't, you'll probably have real trouble.

Sample solutions.