Lab 25: Generating Trees

Implement this lab with the Intermediate Student Language with Lambda.

Make sure you follow The Style we use for the {B,I,A}SL{,+} languages in this class.

Choose the initial Head and Hands, and get started!

Last Time

In the last lab (Lab 24: Accumulating Cards) the first exercise had you build a deck of cards from a list of suits and a list of ranks. Each of the four suits were combined with each of the thirteen ranks for a total of fifty-two cards.

Ex 1: Generalize your solution to build the deck by designing the function cart-prod, which given two lists will build a list of two-element lists representing the Cartesian product of the input. This must be implemented with explicit recursion (no higher-order list functions allowed).

These tests show you the intended functionality. The order of your results may vary, but not the order of the paired elements.

(check-expect (cart-prod '(1 2) '()) '())

(check-expect (cart-prod '() '(1 2)) '())

(check-expect (cart-prod '(1 2 3) '(a b))

'((3 b) (3 a) (2 b) (2 a) (1 b) (1 a)))

(check-expect (cart-prod '(♠ ♥ ♦ ♣) '(2 3 4))

'((♣ 4) (♣ 3) (♣ 2)

(♦ 4) (♦ 3) (♦ 2)

(♥ 4) (♥ 3) (♥ 2)

(♠ 4) (♠ 3) (♠ 2)))

Ex 2: Which type of 2-List template does cart-prod exemplify? Does it iterate over only one list, iterate over one and then the other list, or iterate over both lists in simultaneously?

Ex 3: Re-implement cart-prod using higher-order functions.

Trees with Leaves

It’s easy to represent binary trees using lists.

; A Tree is one of:

; - 'leaf

; - (list Tree Tree)

The symbol 'leaf is a Tree of height 0.

Ex 4: Write down all of the trees of heights 0, 1, and 2. There should be 1, 1, and 3 such trees, resp.

Ex 5: Describe in a comment (and to your partner) how the trees of height 2 are created using the trees of heights 1 and 0. What does it actually mean to be a tree of height 2? What must be true of the subtrees?

Ex 6: Design the function trees= which given a Natural h generates a list of all Trees of height h. Use insights gleaned from Ex 5 to generate the correct recursive calls.

Hint: You may want to also design a function trees<, which returns a list of all Trees of height less than the given Natural h.

Another Hint: You may find the function cart-prod useful in your design of trees=.

WARNING: There are 457653 trees of height 5. You’ll likely run out of memory enumerating the trees of height 6.

Ex 7: Design a function number-of-trees= which given a Natural h, returns the number of trees of that height. You should not have to create the trees (or use trees= at all) to complete this definition. Instead, consider how to generate the number using the same recursive structure as your solution to trees=.