Problem Set 7
Purpose This problem set is focused on the use of higher order functions and trees.
Problem 1 Rewrite Centipede in ISL+λ to use higher-order list processing functions whenever possible. Make sure your program works as well as (or better than!) before, and is as well tested.
Problem 2 Suppose we wanted to keep track of the students in a class, based on their id numbers. We might maintain a [Listof MaybeStudent], such that the value at index i is either a Student with id number i, of false if no such student is in the class. But this is woefully inefficient, because this information is sparse: not every id number maps to a student, and we’ll repetitively store false for millions of indices. Can we do better?
Let’s generalize from Students to arbitrary data. Suppose we organize these important values and their ids in a binary tree structure such that for each node in the tree, all the elements on the left subtree of that node have an id less than the id at that node, and all the elements on the right subtree of that node have an id greater than the id at that node.
; A [PartialListTree X] ([PLT X]) is one of: ; - 'leaf ; - (make-node Natural X [PLT X] [PLT X]) (define-struct node (id val left right)) ; A [PLT X] represents some of the values in a [Listof X] and their indices in the list ; IMPORTANT: Given a PLT p, every node in (node-left p) has id < (node-id p) ; and every node in (node-right p) has id > (node-id p)
(define PLT1 (make-node 0 "Yes" 'leaf 'leaf)) ; A [PLT String] (define PLT2 (make-node 5 'hello (make-node 2 'abc 'leaf 'leaf) 'leaf)) ; A [PLT Symbol] (define PLT3 (make-node 5 16 ; A [PLT Number] (make-node 2 20 'leaf 'leaf) (make-node 10 5 'leaf (make-node 20 0 'leaf 'leaf))))
Design the function update which takes a [PLT X], a Natural i, and a value v of type X. If the given PLT has the id i in it, then we update the value at that id to be v. If the PLT does NOT have the id i in it, we will add in the id,value pair (i,v) at the appropriate location.
(make-node 5 16 (make-node 2 20 'leaf 'leaf) (make-node 10 5 'leaf (make-node 20 6 'leaf 'leaf)))
(make-node 5 16 (make-node 2 20 'leaf 'leaf) (make-node 10 5 (make-node 6 20 'leaf 'leaf) (make-node 20 0 'leaf 'leaf)))
Problem 3 Design the function retrieve which takes a PLT and a Natural i. If the given PLT has the id i in it, then we retrieve the value at that id. If not, we return false. NOTE: You will need to define a new type of data for this problem.
; A [Tree X] is one of: ; - 'leaf ; - (make-tree X [Tree X] [Tree X]) (define-struct tree (val left right))
In class, we discussed how to implement map-tree, that takes a [Tree X] and a [X -> Y] and produces a [Tree Y] that is the same shape as the original tree and contains the results of applying the given function to each item in the tree. Are there other loop functions we could implement on trees?
Problem 4
Design the function filter-tree which takes a [Tree X] and a
function of the form [X -> Boolean] and produces a [Listof X] which contains all
the elements of the tree which produce true for that function. (Hint: think carefully
through the template for this function. What are the signatures for all the expressions
involved —
Problem 5 Design the function fold-tree which takes a [Tree X], a function of the form [X Y Y -> Y], and a base case Y and folds over the elements of the tree in the same way that foldr folds over the elements of a list.
(define TREE1 (make-tree 2 (make-tree 1 'leaf 'leaf) (make-tree 4 (make-tree 3 'leaf 'leaf) (make-tree 5 'leaf 'leaf)))) (check-expect (tree->list TREE1) '(1 2 3 4 5))