Due Date: Friday June 12, 10:00pm EDT
Purpose: To practice trees and mutually recursive data;
You must submit a single .rkt file containing your responses to all exercises via the Handin Server. We do not accept email submissions.
You must use the programming language specified at the top of this page.
Your code must conform to the guidelines outlined in the style guide on the course website. The style guide will be updated as the semester progresses, so revisit it before submitting each assignment.
Unless otherwise stated, for all programming problems you must provide (i) a signature, (ii) a purpose statement, (iii) sufficiently many check-expects (not for big-bang programs), and (iv) the code, in the language specified at the top of this page.
Be sure to look at the feedback for previous assignments before submitting, as we will be grading you more strictly on things we have pointed out before.
(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 Atom is one of: ; - Number ; - String ; - Boolean ; representing an atomic value ; An Sexpr is one of: ; – Atom ; – [List-of SExpr] ; A [List-of SExpr] is one of: ; – '() ; – (cons SExpr [List-of SExpr])
Exercise 4 Design the function contains-same-atoms? that determines if two SExprs contain the same atoms. For example, "a" and (list "a") contain the same atoms as do (list (list "a" (list "b" "b") "c" 2 #true)) and (list 2 "c" #true "b" "a"). "a" and (list "a" "b") do not. Use list abstractions whenever possible.