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
```

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