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.

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) ;;