Comp 210 Lab 6: Mutual Recursion

Index: list, Directory Example

`list`

First, we have a brief aside from our main topic.

The following is a convenient abbreviation shown in class, and already introduced in some lab sections:

     (list 1 3 5 7)
     =
     (cons 1 (cons 3 (cons 5 (cons 7 empty))))

Using list introduces the exact same cons structure, but it is easier for humans to read in big or nested lists, as in some data structures we're now using. When writing programs on lists, you should still think in terms of the cons structure.

Q: What's the difference between (cons 1 empty) and (list 1 empty)?
A: The former creates a list containing one element, 1. The latter creates a list containing two elements, 1 and empty, i.e., the list (cons 1 (cons empty empty)).

Q: What's the difference between (cons 1 2) and (list 1 2)?
A1: The former is an error -- cons's second argument must be a list. The latter creates a list containing two elements, 1 and 2, i.e., the list (cons 1 (cons 2 empty)).
A2: For the curious... There is another answer if we consider all of Scheme. However, we won't be talking about that in this course.

Q: What's the difference between (cons 1) and (list 1)?
A: The former is an error -- cons requires two arguments. The latter creates a list containing one element, 1.

Q: What's the difference between (cons 1 2 empty) and (list 1 2 empty)?
A: The former is an error -- cons requires two arguments. The latter creates a list containing three elements.

Q: What is (list)?
A: empty.

In short, cons and empty are the constructors of lists. list is another function which makes lists, and is convenient shorthand for combinations of the constructors.

Directory Example

The following are data definitions for for a simplified representation of files and directories, as seen in class:

     A file is a symbol (its name).

     A directory is a structure
       (make-dir name contents)
     where name is a symbol, and contents is a l-o-f-d.

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

Observe the mutual recursion between directories and list-of-files-and-directories.

This is just another example of a tree data structure. We warned you trees were common!

Also, as seen in class, the following are the corresponding templates:

     ;(define (dir-fn a-dir)
     ;  ...(dir-name a-dir)...
     ;  ...(lofd-fn (dir-contents a-dir))...)

     ;(define (lofd-fn a-lofd)
     ;  (cond
     ;    [(empty? a-lofd)
     ;     ...]
     ;    [(file? (first a-lofd))
     ;     ...(first a-lofd)...(lofd-fn (rest a-lofd))...]
     ;    [(dir? (first a-lofd))
     ;     ...(dir-fn (first a-lofd))...(lofd-fn (rest a-lofd))...]))

To do:

Develop a function
```
     ; find? : directory file -> boolean
     ; Returns whether the given file is in the directory or one
     ; of its subdirectories.
     
```
Note that this is a vast simplification of find, the mother-of-all everything-but-the-kitchen-sink UNIX directory traversing command.

Develop a function

     ; flatten-dir-once : directory symbol -> (directory or l-o-f-d)
     ; Returns a structure like the original directory, except that the
     ; named directory is removed, with its contents moved up one level.

Here are two pictorial examples, in both cases removing the directory named to-remove.

	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.

If you still have time, develop a function
```
     ; any-duplicate-names? : directory -> boolean
     ; Returns whether any 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. There's a more efficient way that follows a template we'll introduce later in the course.

For the very curious... Develop a program to check for duplicated names among all directories and files in the given tree. Here's a hint.
For the curious... Give more accurate data definitions for modeling UNIX directories and files. Files have not only names, but contents and other properties, such as an owner and last-modified date. Furthermore, a directory is considered to be a kind of file.

Here are solutions.