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.

Setup instructions #

Head to http://url.cs51.io/lab6 and follow the Lab Procedures.

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