Lab 9 Mutual Recursion

Purpose: to practice working with mutually recursive data

Textbook references: Chapter 19.1: Trees, Chapter 19.4 Designing with Intertwined Data, Chapter 20: Incremental Refinement

Binary Trees (BTs)

Revisit the binary family tree data from the lecture:

(define-struct person [name parent1 parent2])

; A Person is one of:

; - String

; - (make-person String Person Person)

; repr. a person: either

; - with a name but no (known) parents, or

; - with a name and two parents.

(define person-1 "Alice")

(define person-2 "Bob")

(define person-3 "Carol")

(define person-4 "Dean")

(define person-5 (make-person "Egan"   person-1 person-2))

(define person-6 (make-person "Fiona"  person-3 person-4))

(define person-7 (make-person "Gerald" person-5 person-6))

Exercise 1 Design a function tree->list that flattens the family tree: it returns the list of names of family members, as a [List-of String].

Caution: your check-expects may fail if your check-expects return the family members in the "wrong" order: When we design the tests we don’t know the order in which the function will return the elements, and we don’t want to know: the tests should not depend on implementation details of the function. What can we do about this?

Exercise 2 Modify the above person structure such that we accommodate the case of a person for whom only one parent is known. That is, each node has zero, one, or two successors (= known parents).

For this problem, do not use a list to represent the zero, one, or two known parents. Instead, explicitly allow a third case in the definition of Person, analogous to the "name-only" case.

Exercise 3 Design a function perfect-bt? that checks whether a given BT is perfect, which means that every node has either zero or two successors. For example, Alice’s family tree is perfect. Obviously, in the previous exercise, include some examples of binary family trees that are not perfect, so you can use them as tests in the present exercise.

Exercise 4 Design a function complete-bt that checks whether a given BT is complete, which means that it is perfect, and leaves (nodes without successors) are only allowed at the bottom layer. More precisely, a BT is complete if there exists a number n such that every node at distance n from the root is a leave, and every other node has exactly two successors. For example, Alice’s family tree is complete (choose n=2).

Bonus question: how many nodes does a complete BT have?

Arbitrary numbers of successors

Exercise 5 Design data AE to represent a simple arithmetic expression. An AE is either a number, or a sum of any number of operands, or a difference of any number of operands, or a product of any number of operands, or a quotient. In contrast to the other operators, a quotient AE must have at least one operand.

Represent each non-number AE as consisting of the operator (represented as a String: "+" "-" "*" "/") and a list of operands.

Exercise 6 Write a function eval that takes an AE as input and evaluates it, i.e. it computes its value. Numbers of course evaluate to themselves, and non-number AEs evaluate according to the standard semantics of the mathematical operators. Special rules: the empty sum and the empty difference evaluate to 0, the empty product evaluates to 1, and the single-operand quotient evaluates to the reciprocal value of the operand: (/ a) = 1/a. If given more than one operand, a quotient evaluates to the first operand divided in sequence by all the others: (/ a b c) = a/b/c.

Warning: as per the Piazza post, do not use the apply function (which wouldn’t even work for this exercise).