CS18 Bridge Assignment: Files and Directories

[Work in Pyret, putting your work in a file called filesystem.arr]

Imagine that you wanted to write programs for managing directories and files on a computer. Each directory has a name and can contain both subdirectories and files. Each file has a name and size.

Your goal is to design data structures (Pyret datatypes) to capture files and directory hierarchies, then to write a series of functions that process directory hierarchies (starting from a single “top-level” directory, like a Documents/My Documents folder).

As always, you should write tests for your functions.

  1. Propose Pyret datatypes that will capture nested directories and files. You may assume that there is one top directory that all other files/directories lie within.

    The design of this data structure is itself a challenge. We want you to try to design this, put your best version in a comment at the top of your file, then look at the one we’re providing. By submitting your best version from before you looked at ours, you give us the chance to give you some feedback on data structure design on a more challenging problem.

  2. Write a function count-files that takes a single top-level directory and returns a number indicating how many files are nested somewhere within that directory (no matter how deep).

  3. Write a function any-empty-dirs that takes a single top-level directory and returns a boolean indicating whether any directory within the hierarchy is empty (has no files and no subdirectories).

  4. Write a function find-path that takes a single top-level directory and the name of a file and returns a list of the (sub)directories that one must open in order to find the named file, or false if the given filename is not within the directories. Assume that the given filename is in your system at most once.

    For example, if you had a directory for cs111 homework containing a subdirectory for each assignment, then

    find-path(cs111-dir, "hwk4code.arr")

    would return [list: "CS111", "hwk4"] (assuming hwk4code.arr is in the hwk4 directory)

    Hints:

    (1) Work with examples as you do this – this problem can easily get a lot harder than it should if you don’t figure out how to leverage the recursion, and examples can help you do that. Write several examples for different cases before you try to write code.

    (2) Note that the problem has you return a list in some cases (found the file) and false in others (didn’t find the file). Remember that Pyret lets you omit the return type of a function. Do that, and you can return either boolean or a list.

    (3) Follow templates.

    (4) Get the easy cases working, then fill in the harder ones. Post questions if you want to check whether you are heading along the right track. Planning this out and taking it step by step will probably save you a ton of time on this assignment.