Assignment 9
Due Date Tuesday 6/11 at 10:00pm
Purpose To design functions that process mutually recursive data and trees.
Graded Exercises
(define-struct leaf []) (define-struct node [data left right]) ; A [Tree X] is one of: ; - (make-leaf) ; - (make-node X [Tree X] [Tree X]) (define-struct person [name yob]) ; A Person is a (make-person String Number) ; - where name is the person's name ; - and yob is their year of birth ; An FT is a [Tree Person] and represents a family tree, with the youngest person at the root.
Exercise 1 Design mirror which takes any tree and flips all of its right/left branches all the way down the tree.
Exercise 2 Design names which takes an FT and returns a list of all of the names of the people in the tree. A name may appear more than once if two people in the tree have the same name.
Exercise 3 Abstract mirror and names and use this abstraction to redefine mirror and names (leave the old versions commented out).
; An Sexpr is one of: ; – Symbol ; – Lexpr ; A Lexpr is one of: ; – '() ; – (cons Sexpr Lexpr)
Exercise 4 Design the function contains-same-symbols? that determines if two Sexprs contain the same symbols. For example, 'a and '(a) contain the same symbols as do '((a (b b) c)) and '(c b a). 'a and '(a b) do not. Use list abstractions whenever possible.