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 or tips about the course? Let us know: heads@cs51.io.

## Setup instructions #

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

## Lab puzzle #

Today’s lab puzzle concerns this 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) ;;