Recitation 003

Associative:

f(f(x, y), z) = f(x, f(y, z))

Identity:

f(b, x) = x = f(x, b)

We can relax the constraint on identity. It only need to be an identity during execution of the function.

ParenMatch using Scan

Note that the scan includes base case while scanInc does not include base case, but put the last element into the output sequence.

We can implement ParenMatch using scan. We just scan the sequence and make sure there is nothing below 0 during the scan.

fun parenMatch (parens : Paren.t Seq.t) : bool =
   let
     val nums = Seq.map (fn Paren.L => 1 | Paren.R => ~1) parens
     val (prenums, final) = Seq.scan (op+) 0 nums
     val valid = Seq.map (fn i => i >= 0) prenums
   in
     (Seq.reduce (fn (a, b) => a andalso b) true valid) andalso final = 0
   end

Group Dinner

A group of n friends sit around a circular table at a restaurant. Some of them know what they want to order; some of them don’t. The ones who don’t know what to order decide to pick the same thing as the person on their left.

// TODO: receive solution from TAs

Table of Content