Homework 10

home work!

Programming Language ISL+

Due Date: Friday June 12, 10:00pm EDT

Purpose: To practice trees and mutually recursive data;

(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.