Homework 4

Due Date Sunday October 30 at 11:00 pm

Purpose To work with recursive tree structures.

Sets

We developed in class a library for dealing with sets that assumed sets were represented by lists of elements. While this works, it would be too slow for most use-cases. Below, we ask you to redefine the functions we have defined so far (empty-set?, set-contains?, etc.) by replacing the list-based representation with a binary-tree-based representation, to improve the overall performance of our library.

Here’s the definition of a binary tree as we discussed in class:

; A ToN (Tree of Numbers) is one of:

; - 'empty

; - (make-node ToN Number ToN)

; Invariant: All numbers in left  child < than node's value.

;            All numbers in right child > than node's value.

(define-struct node [left val right])

This is an exercise in abstraction. A programmer who initially uses the list-based implementation above should be able to switch to the binary-tree-based implementation without otherwise modifying their code.

To assist you, here is the code for the list-based set library:

; A SoN (set of numbers) is one of:

; - empty

; - (cons Number SoN)

; We choose order irrelevant, repetition allowed.

; SoN -> Boolean

; Is the set empty?

(define (empty-set? son) (empty? son))

; To/from lists

; LoN -> SoN

; SoN -> LoN

(define (list->set lon) lon)

(define (set->list son)

(cond [(empty? son) '()]

[(set-contains? (rest son) (first son))

(set->list (rest son))]

[else (cons (first son) (set->list (rest son)))]))

; SoN Number -> Boolean

; Does the set contain the element x?

(define (set-contains? set x)

(and (not (empty-set? set))

(or (= x (first set))

(set-contains? (rest set) x))))

; SoN Son -> Boolean

; Is the set "a" a subset of the set "b"?

(define (subset? a b)

(or (empty-set? a)

(and (set-contains? b (first a))

(subset? (rest a) b))))

; SoN Son -> Boolean

; Are the sets equal?

(define (set-equal? a b)

(and (subset? a b)

(subset? b a)))

; SoN Number -> Son

; Add the number to the set.

; Slower, but less prone to gratuitous storage blowup.

(define (set+elt s x)

(if (set-contains? s x)

s

(cons x s)))

; SoN SoN -> SoN

; Compute the union of the two sets

(define (union a b)

(cond [(empty-set? a) b]

[else (set+elt (union (rest a) b)

(first a))]))

; SoN SoN -> SoN

; Compute the intersection of the two sets

(define (intersection a b)

(cond [(empty-set? a) empty-set]

[(set-contains? b (first a))

(set+elt (intersection (rest a) b)

(first a))]

[else (intersection (rest a) b)]))

To be clear: for all of the exercises in this section, when they say "set", they mean a binary-tree-based representation of a set as we discussed in class. In other words, replace the definition of a Set of Numbers from above with this one:

; A SoN (Set of Numbers) is a ToN (Tree of Numbers)

Exercise 1 Define an appropriate constant empty-set and design the function empty-set? that determines if a given set is empty.

Exercise 2 Design the functions list->set and set->list that convert a list of numbers into a set of numbers, and that list the numbers in a set, respectively.

Exercise 3 Design the function set-contains? that takes a set and a number and returns true if the number is in the set.

Exercise 4 Design the function subset? that takes two sets as input and determines whether the first set is a subset of the second subset.

Exercise 5 Design the function set-equal? that takes two sets as input and determines if the two sets contain the same elements.

Exercise 6 Design the function set+elt that takes a set and a number as input and returns the set with the number added to it.

Exercise 7 Design the function union that takes two sets as input and returns their union.

Exercise 8 Design the function intersection that takes two sets as input and returns their intersection.

Leafy Binary Trees

A leafy binary tree is a binary tree with the symbol 'leaf at its leafs (as opposed to, say, a number), and nodes that store only the left and right branches (but no other value, such as a number). In other words, only the structure of the tree distinguishes it from other leafy binary trees.

Exercise 9 Design a function that consumes a natural number n and creates (a list of) all the leafy binary trees that have height n. The height of the tree is the maximal number of steps from the root of the tree to one of its leaves (e.g. the tree consisting of just one leaf has height 0).

Hint: Design a function that consumes a natural number n, and creates (a list of) all leafy binary trees of height equal or less than n.

Hint: If you have to use filter to remove things from the list, you’re working too hard.

Hint: It might be helpful to draw pictures.

Note: this is not about abstraction; it’s a kind of puzzle that will exercise your ability to think recursively. (We hope you) Have fun...