Lab 10 Wait... Lists are just Trees are just S-Expressions?
Always have been...
Purpose: Practicing with trees, mutually referential data, and abstractions on them.
Textbook references: Chapter 14: Trees, Chapter 15: Mutually Recursive Data
Lists are soooo linear
(define-struct leaf []) (define-struct node [value left middle right]) ; A [3Tree-of X] is one of: ; - (make-leaf) ; - (make-node X [3Tree-of X] [3Tree-of X] [3Tree-of X]) ; Interpretation: ; A [3Tree-of X] is either a leaf (which contains no information) ; or a (make-node v l m r) that has some value and left, middle, ; and right subtrees. (define leaf-tree (make-leaf)) (define tree1 (make-node 1 (make-leaf) (make-node 2 (make-leaf) (make-leaf) (make-leaf)) (make-node 3 (make-leaf) (make-leaf) (make-leaf))))
Exercise (Reviewed) 1 Write the template for a [3Tree-of X].
Exercise 2 Trees are just like lists but with a more interesting and flexible structure. So it stands to reason that we can create abstractions over trees like we do for lists. Write just the signatures for the following functions:
3tree-map: Given a tree and a function to transform the data at each node, return a tree with the given function applied to the value at every node.
3tree-ormap: Given a tree and a predicate, return whether any node’s value in the tree passes the given predicate.
Don’t go implementing these functions just yet! Check in with a tutor/TA in your assigned group channel to check your signatures before moving forward.
Exercise 3 Complete the remaining steps of the Design Recipe for 3tree-map and 3tree-ormap.
Exercise 4 Design a function 3tree-grab-x-coords which, given a [3Tree-of Posn] returns a tree with just the x-coordinates of each node.
Exercise 5 Design a function 3tree-count, which accepts a tree and a predicate and counts the number of nodes in the tree whose values pass the predicate. Hint: use the [3Tree-of X] template.
Abstracting further
Trees are great, but what if we want an arbitrary number of children at each node? Well, this is exactly an s-expression! In this section, we’ll see just how useful s-expressions are in representing different data by looking at a nearly-equivalent data defininition.
Below is a representation of a filesystem.
(define-struct file [name data]) (define-struct dir [name contents]) ; A FSC (FileSystemComponent) is one of: ; - (make-file String String) ; - (make-dir String [List-of FSC]) ; INTERPRETATION: ; a (make-file n d) represents a file with name n and data d ; a (make-dir n fscs) represents a directory with name n and contents fscs
Exercise 6 Write the template for a FileSystemComponent. Check in with your tutor/TA before moving forward.
Exercise 7 Design the function file-count, which determines the total number of files in a FileSystemComponent.
Exercise 8 Design the function find-deepest-directory-depth which given a FSC determines the deepest number of layers a directory is nested anywhere in the filesystem.
Exercise 9 Recall the definition of a [Maybe X].
; A [Maybe X] is one of: ; - #false ; - X Design the function find-full-path-to-file which accepts a FSC and a file name and returns a [Maybe String] representing the full path to the file, and #false if a file with the given name does not exist. For example, a file called foo.rkt in the directory homework in the directory documents has the path "documents/homework/foo.rkt"
Exercise 10 Design the function draw-filesystem which draws an image representation of a given filesystem. The exact aesthetics are up to you, but the image should clearly convey the structure of the filesystem, along with the names of the directories and files. Include how many files are contained within a directory. Here’s a beautiful example of what this could look like:
