Lab 6

# Lab 6 Instructions #

## Reminders #

• While other students are coming into class, follow the setup instructions below. (But please wait until you’re instructed before beginning work on the lab.)

• Don’t move on from a problem until both partners agree. If you and your partner are stuck in lab, your tablemates can help, and you can help your own understanding by explaining things to them.

• High five when you solve a problem. The endorphins lock in the knowledge.

• One laptop at a time (unless you’re using one for reference materials).

• Do you have hints about the course? Let me know: shieber@seas.harvard.edu.

## Lab puzzle #

Here’s an algebraic data type for polymorphic binary trees that store values at the leaves and at the nodes:

  type ('a, 'b) bintree =
| Leaf of 'a
| Node of 'b * ('a, 'b) bintree * ('a, 'b) bintree ;;


The following function generates these trees:

  let rec gen n b =
if n = 0 then Leaf b
else if n = 1 then Leaf (not b)
else Node (n, gen (n - 1) b, gen (n - 2) b) ;;


How many leaves are in the tree generated by the call gen 6 false?

A. 4 or fewer

B. 5

C. 6

D. 7

E. 8

F. 9

G. 10

H. 11

I. 12

J. 13

K. 14

L. 15 or greater