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 calledtotal
that consumes a FileSystemfs
and produces the total number of files infs
.Exercise 2:
Design a function that consumes a FileSystem and a File and returnstrue
if the file is present in the FileSystem andfalse
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 d2Exercise 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.ssExercise 4:
Design a function that consumes a Dird
and produces the total number of files in the whole directory tree ofd
. For instance, the directory in the previous exercise contains 11 files.Exercise 5:
Design a function that consumes a Dird
and a Filef
and returnstrue
iff
exists anywhere in the directory tree, i.e. ind
or any of its subdirectories, andfalse
otherwise.Exercise 6:
Design a function that consumes a Dird
and two Filessrc
andtarget
, and produces a Dir which has the same files asd
but with all files namedsrc
renamed totarget
.
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 Dird
and produces the total number of files (just files, not directories) in the directory tree ofd
.Exercise 8:
Design a function that consumes a Dird
and a Strings
representing an owner and returns a list of files owned bys
in the directory tree ofd
.Exercise 9:
Design a function that consumes a Dird
and a Numbern
representing file size and returns a list of files in the directory tree ofd
with size at leastn
.Exercise 10:
Design a function that consumes a Dird
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!