Comp 210 Lab 5: Mutual Recursion

Index: list, Directory Example

`list`

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

The following is a convenient abbreviation:

     (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.

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 UNIX directory traversing commands.

Develop a function

     ; flatten-dir : 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 a couple 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.

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. A directory is considered to be a kind of file.

Here are solutions.