Lecture 11: More Directions

###
Lecture 11: More Directions

1. Recall the last data definition:

                [The Einstein Model of File Systems]

       (define-struct dir (name size subs))

             ____________________________________________________________________
            |                                                                    |
            v                                                                    |
       A directory is (make-dir symbol number list-of-directories) |
                 __________________________________________________              |
                |                                                  |             |
                v                                                  |             |
       A list-of-directories is either                             |             |
         - empty                                                   |             |
         - (cons d lod)                                            |             |
         where d is a directory and lod is a list-of-directories.  |             |
                       |                          |                |             |
                       |                           ----------------              |
                        ---------------------------------------------------------

2. Develop the program

       ;; du : directory -> number
       ;; du computes the total disk usage of the directory by adding up all
       ;; directory sizes in a-dir
       (define (size a-dir) ...)

   Since there are two data definitions, we need TWO templates:

   1. one for directory-consuming programs
   2. one for list-of-directories-consuming programs.

   Annotate them with mutual and self-references. These refs have the same structure as those in the data definitions.

   Fill in the blanks.

   Develop a program that also adds up file sizes

   now add list-of-files to directory as a separate field; new mutual references; extend du a final time. This is pretty close to the real Unix du now!

3. Exercise: Develop a program that computes the "path" into a directory to find a given file name. [mention, optional]

       ;; path : dir symbol -> (listof name)
       ;; compute the list of directory names that leads to the first occurrence
       ;; of file-name in a directory contents -- empty if it doesn't exist
       (define (path a-dir file-name) ...)

       (define MS (make-directory 'win3.1 empty empty))
       (define Nxt (make-directory 'win empty 'world)
       (define Sys (make-directory 'sys (list Nxt MS) 'world))

       (path  MS 'world) =  empty

       (path Nxt 'world) = (list 'win)

       (path Sys 'world) = (list 'sys 'win)

4. Simplify the problem. Here: Let's tackle the simpler problem of testing whether the directory exists:

       ;; in-dir : directory symbol -> bool
       ;; determines whether directory with a-name occurs in a-dir
       (define (in-dir? a-dir name)
         (cond
           [(eq? (dir-name a-dir) name) #t]
           [(in-subs? (dir-subs a-dir) name) #t]
           [else #f]))

       ;; in-dir : list-of-directories symbol -> bool
       ;; determines whether directory with a-name occurs in the list of directories
       (define (in-subs lod name)
         (cond
           [(empty? lod) #f]
           [else (or (in-dir? (first lod) name)
       	      (in-subs? (rest lod) name))]))

   Now compare the self-references in these two functions with those of the data definitions.
5. Now you can tackle the rest:

       (define (path-in-dir a-dir name)
         (cond
           [(in-files (dir-files a-dir) name) (list (dir-name a-dir))]
           [(in-subs (dir-subs a-dir) name)
            (cons (dir-name a-dir) (path-in-subs (dir-subs a-dir) name))]
           [else empty]))

       (define (path-in-subs lod name)
         (cond
           [(empty? lod) '???]
           [else
             (cond
       	[(in-dir (first lod) name)
       	 (path-in-dir name)]
       	[else
       	  (path-in-subs (rest lod) name)])]))

6. Sometimes a program must process two complex inputs at once:

       ;; f : (listof symbols) (listof numbers) -> ???
       ;; f combines symbols and numbers into records and ...
       (define (f aloS aloN) ...)

   use two-dimensional analysis to figure out the conditionals---Cartesian product of choices!

   | (empty? aloN) | (cons? aloN)
   (empty? aloS) |  |
   (cons? aloS) |  |

       ;; f : (listof symbols) (listof numbers) -> ???
                    ______________________________________
                          _____________________________   |
                   |     |			       	|  |
                   v     v				|  |
       (define (f aloS aloN) 				|  |
         (cond						|  |
           ((and (empty? aloS) (empty? aloN)) ...)	|  |
           ((and (cons? aloS)  (empty? aloN))		|  |
            ... (first aloS) ...			|  |
            ... (rest aloS) ...) -------------------------|
           ((and (empty? aloS) (cons? aloN))		|  |
            ... (first aloN) ...			|  |
            ... (rest aloN) ...) ----------------------|  |
           (else					|  |
             ... (rest aloN) ... ----------------------   |
             ... (rest aloS) ... -------------------------
             ... (first aloN) ...
             ... (first aloS) ...
             )))

   There are many different recursions possible now:

        (f aloS (rest aloN))
        (f (rest aloS) aloN)
        (f (rest aloS) (rest aloN))

   Some functions need one of them; some functions need all three of them.

   Here are two recommended little exercises that bring out the idea:

       #|
          zip : (listof symbols) (listof numbers) -> (listof (list names numbers))
          (define (zip names phones) ...)

          Purpose: combines corresponding items on the two lists, names and
          phones, into `pairs' i.e. lists of two items

          Example: (zip (list 'a 'b 'c) (list 0 1 2))
                 = (list (list 'a 0)
       	          (list 'b 1)
       		  (list 'c 2))

          When the list are of different length, zip calls error with the first
          item on the list that has left-over elements.
       |#

   Define the function merge, which consumes two sorted lists of numbers and produces a single sorted list of numbers w/o duplicates.

       #|
          merge : (listof number) (listof number) -> (listof number)
          (define (merge l1 l2) ...)

          Assumption: both l1 and l2 are sorted in ascending order
          and are duplicate free

          Purpose: produce a single list of all numbers in l1 and l2
          in ascending order; if l1 and l2 each contain the same number
          only include one in the result

          Example: (merge (list 0 3 4 5) (list 1 2 3 9))
                 = (list 0 1 2 3 4 5 9)
       |#

Matthias Felleisen | This page was generated on Fri Mar 5 09:04:41 CST 1999.