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:

Setup instructions #

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