1 def simp(r: Rexp): (Rexp, Val => Val) = r match {

     2   case ALT(r1, r2) => {

     3     val (r1s, f1s) = simp(r1)

     4     val (r2s, f2s) = simp(r2)

     5     (r1s, r2s) match {

     6       case (NULL, _) => (r2s, F_RIGHT(f2s))

     7       case (_, NULL) => (r1s, F_LEFT(f1s))

     8       case _ => 

     9          if (r1s == r2s) (r1s, F_LEFT(f1s))

    10          else (ALT (r1s, r2s), F_ALT(f1s, f2s)) 

    11     }

    12   }

    13   ...

    14 }

    15 

    16 def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v))

    17 def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v))

    18 def F_ALT(f1: Val => Val, f2: Val => Val) = 

    19   (v:Val) => v match {

    20     case Right(v) => Right(f2(v))

    21     case Left(v) => Left(f1(v)) }