Fundamentals of Computer Science I

Lab 10 - List Recursion for Files and Directories

Remember:

• Work in pairs
• Change roles often
• Follow the design recipe for every problem

---

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 String

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

Exercise 1:

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

Exercise 2:

Design a function that consumes a FileSystem and a File and returns true if 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 allow directories as well.

;; A File is a String

;; 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 the directory containing the file f and all the 
;;    items of directory d
;;  - (cons d1 d2) creates the directory containing the subdirectory d1 and all
;;    the items of directory d2

Exercise 3:

Construct a Dir that represents the following directory tree. Note that our simple data definitions don't allow names for directories.

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

Exercise 4:

Design a function that consumes a Dir d and produces the total number of files in the whole directory tree of d. For instance, the directory in the previous exercise contains 11 files.

Exercise 5:

Design a function that consumes a Dir d and a File f and returns true if f exists anywhere in the directory tree, i.e. in d or any of its subdirectories, and false otherwise.

Exercise 6:

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 still minimal. Let's add attributes to files and directories so we can track who owns a file and what its size is on disk:

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

Let's also add names to directories and split their contents into two separate pieces, a list of subdirectories and a list of files:

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

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

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

Exercise 7:

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.

Exercise 8:

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

Exercise 9:

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 at least n.

Exercise 10:

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.

---

Displaying directory trees

Exercise 11:

Design a function that draws a file as an image. It has to show the name, the size and the owner of a file.

Exercise 12:

Design a function that draws a directory. It has to show the name of the directory and show all the files that reside inside this directory.
Hint: your previous function could come in handy!

Exercise 13:

Extend the function you defined in exercise 12 to also show the contents of subdirectories.

Enjoy!