CS 2500 Honors Lab 4: Recursion

New lab partners, new friends

It is time to switch lab partners! You may not work with a partner with whom you have previously worked this semester. Choose someone you haven't already worked with and relocate so that the two of you are sharing a single workstation.

Switching pilot and co-pilot

In previous labs you were switching pair-programming roles in-between exercises. In this lab and in future labs, you will switch roles at regular intervals throughout the lab. The teaching assistants and tutors will announce that it is time to switch roughly every fifteen minutes.

DR uber alles

Remember to practice using the design recipe for every problem!

Don't Use IE

You will be unable to see the exercise numbers if you use IE.

A Simple Filesystem

As computer users we can create files and directories (sometimes called folders) on our computers to store our data and our programs. It is useful to have operations that allow manipulating these files and directories. Consider the following data definition of a flat FileSystem (FS), i.e., no directories, just files.

;; A File is a Symbol

;; An FS (FileSystem) is one of
;; -- empty
;; -- (cons File FS)

1. Design a function called total that consumes a FileSystem fs and produces the total number of files in fs.

1. Design a function that consumes a FileSystem and a File and returns true if the the file is present in the FileSystem and false otherwise.

Adding Directories to our Filesystem

Flat FileSystems quickly become chaotic. We would instead like to have a hierarchical way to structure our files on our machines. So we extend our previous data definition to accommodate for directories as well.

;; A File is a Symbol

;; A Dir is one of
;; -- empty
;; -- (cons File Dir)
;; -- (cons Dir Dir)

;; A Dir is constructed by gradually adding files and directories together:
;;  - (cons f d) creates a directory adding file f to the contents of directory d
;;  - (cons f (cons d empty)) creates a directory containing file f and subdirectory d
;;  - (cons d1 d2) creates a directory adding subdirectory d1 to the contents of directory d2
;;  - (cons d1 (cons d2 empty)) creates a directory containing subdirectories d1 and d2

1. Construct a Dir that represents the following directory tree:

   - hw3.ss
   - hw1.ss
   + scratch
     - lists-and-recursion.ss
     - structs.ss
     - tetris.ss
   - syllabus.pdf
   + misc
     - olin.png
     - amal.png
     - r6rs.pdf
     - kitteh.png
   - hw2.ss
   

1. Design a function that consumes a Dir d and produces the total number of files in the whole directory tree of d.

1. Design a function that consumes a Dir d and a File f and returns true if f exists in d or any of its subdirectories and false otherwise.

1. Design a function that consumes a Dir d and two Files src and target, and produces a Dir which has the same files as d but with all files named src renamed to target.

Adding Attributes to Files and Directories

Directories gave us more structure but the information that we have for each file and directory is minimal. Let's add attributes to files and directories.

(define-struct file (name size owner))
;; A File is (make-file Symbol Number Symbol)
;; (make-file s n o) creates a File with name s, size n kilobytes, and owned by o.

For a directory we will split its contents into two pieces: one for a list of files and the other for a list of subdirectories.

;; An LoF (List-of-Files) is one of
;; -- empty
;; -- (cons File LoF)

(define-struct dir (name dirs files))
;; A Dir is a (make-dir Symbol LoD LoF)
;; (make-dir s ds fs) creates a Dir with name s containing ds as its list of
;; directories and fs as its list of files.

;; An LoD (List-of-Dir) is one of
;; -- empty
;; -- (cons Dir LoD)

1. Design a function that consumes a Dir d and produces the total number of files (just files, not directories) in the directory tree of d.

1. Design a function that consumes a Dir d and a Symbol s representing an owner and returns a list of files owned by s in the directory tree of d.

1. Design a function that consumes a Dir d and a Number n representing file size and returns a list of files in the directory tree of d with size greater or equal to n.

1. Design a function that consumes a Dir d and computes the total size of all files in the whole directory tree. You may assume that directories take up no space.

If you finish early, try tweaking the code to better understand what was given. Enjoy!