Lab 16: Lists qua Filesystem

Implement this lab with the Intermediate Student Language.

Make sure you follow The Style we use for the {B,I,A}SL{,+} languages in this class.

Choose the initial Head and Hands, and get started!

A List by Any Other Name

Directories are a bit like lists with some metadata.

(define-struct file (name content))

; A File is a (make-file String String).

; Interp: Represents a file with a name and some arbitrary content.

;

(define-struct dir (name contents))

; A Directory is a (make-dir String [Listof FileOrDir])

; Interp: Represents a named container for an arbitrary amount of files or

;         directories.

;

; A FileOrDir is one of:

; - File

; - Directory

; Interp: Either a file or directory.

Ex 1: Write down the template for each of File, Directory, FileOrDir, and [Listof FileOrDir]. Be sure to reference the file-template and the directory-template in your file-or-dir-template.

To get you started, here are the examples representing the root directory ROOTDIR, DIR3, DIR0, FILE4, and FILE0:

(define FILE4 (make-file "FILE4" ""))

; (define FILE3 ...)

; (define FILE2 ...)

; (define FILE1 ...)

(define FILE0 (make-file "FILE0" "To be, or not to be: that is the question"))

(define DIR3 (make-dir "DIR3" '()))

; (define DIR2 ...)

; (define DIR1 ...)

(define DIR0 (make-dir "DIR0" (list FILE0)))

(define ROOTDIR (make-dir "" (list DIR0 DIR1 DIR3)))

Counting Files and Directories

Ex 3: Design a function num-children that returns the number of files or directories found directly inside the given directory.

(check-expect (num-children ROOTDIR) 3)

(check-expect (num-children DIR0) 1)

(check-expect (num-children DIR3) 0)

Ex 4: Design a function num-descendents that returns the number of files or directories found at any level inside the given directory.

(check-expect (num-descendents ROOTDIR) 9)

(check-expect (num-descendents DIR0) 1)

(check-expect (num-descendents DIR1) 5)

Looking for Files and Directories

Swap Head and Hands!

Ex 5: Design a function file-exists? that, given a directory and a string name, returns #true if a file with the given name exists inside the given directory or any of its subdirectories.

Ex 6: Design a function dir-exists? that, given a directory and a string name, returns #true if a directory with the given name exists inside the given directory or any of its subdirectories.

Ex 7: Design a function file-or-dir-exists? that, given a directory and a string name, returns #true if a file or directory with the given name exists inside the given directory or any of its subdirectories.

Listing Files and Directories

Ex 8: Design a function all-file-names that returns a list of file names found inside the given directory and any of its subdirectories. The order in which the file names are returned is not important.

Ex 9: Design a function all-dir-names that returns a list of directory names found inside the given directory and any of its subdirectories. The order in which the directory names are returned is not important.

Ex 10: Design a function all-names that returns a list of all file or directory names found inside the given directory and any of its subdirectories. The order in which the file or directory names are returned is not important.

Looking at Files in Directories

Swap Head and Hands!

Ex 11: Design a function file-size that returns the number of characters inside the content of the given file.

(check-expect (file-size FILE4) 0)

(check-expect (file-size FILE0) 41)

(check-expect (file-size (make-file "foo" "foo!")) 4)

Ex 12: Design a function dir-size that returns the sum of the sizes of all files inside the given directory and its subdirectories.

Bonus: Abstract Operations on Files in Directories

These are a bit trickier, but if you follow your templates you shouldn’t have too much of a problem.

Ex 13: Design a function map-files : [File -> X] Directory -> [Listof X] that, given a function file->x and a directory, returns a list containing the results of applying file->x to each file in the given directory or any of its subdirectories.

Ex 14: Design a function filter-files : [File -> Boolean] Directory -> [Listof File] that, given a function test? and a directory, returns a list all files in the given directory and any of its subdirectories for which test? applied to that file is #true.

Ex 15: Design a function fold-files : [File X -> X] X Directory -> [Listof X] that, given a function combine : File X -> X, a base value X and a directory, returns the result of applying combine to each file and recursive result of fold-files in the given directory and any of its subdirectories.

Ex 16: Reimplement the functions map-files and filter-files in terms of fold-files.

Hint: If you’ve never implemented the list operations map and filter in terms of foldr, do that first!