Lab 6: Lists and Arbitrary Recursive Functions

• Work in Pairs
• Change roles often
• Follow the design recipe.

A Simple Filesystem

As computer users we can create files and directories (sometimes also called folders) on our computers to store our data and our programs. It is useful to have operations that allow the manipulation of 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)
   

Exercise 1: Give at least 3 examples of a FileSystem

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

Exercise 3: 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 can become chaotic. We would like to have a more hierarchical way we can structure our files on our machines. So we extend our previous data definition to accommodate for directories (folders) as well

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

    ;; A Dir is constructed by gradually adding files and directories to its contents. 
    ;; (cons f d) constructs a new directory that includes the file f and the contents of d. 
    ;; (cons d1 d2) constructs a new directory that includes the subdirectory d1 and the contents of d2. 
    
   

Exercise 4: Translate the following examples of directory trees into data using the data definition of Dir. (show them 3 or 4 on the projector).

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

Exercise 6: 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.

Exercise 7: Design a function that consumes a Dir d and two Files src and target. The function produces a Dir which has the same files as d but with files named src renamed to target.

Quiz

• Turn off your monitors
• Closed book, closed notes
• The quiz starts when the TA says so and not as soon as you get the quiz
• No talking and no surfing the web until all quizes have been handed in

Adding 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 
    ;; o as the file's owner.  
   

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) 
   

Exercise 8: Design a function that consumes a Dir d and produces the total number of files in directory tree of d.

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

Exercise 10: 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.

Exercise 11: 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 do not take up space, only files take up space.