1 def F_ID(v: Val): Val = v

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

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

     4 def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {

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

     6   case Left(v) => Left(f1(v))

     7 }

     8 def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {

     9   case Seq(v1, v2) => Seq(f1(v1), f2(v2))

    10 }

    11 def F_SEQ_Empty1(f1: Val => Val, f2: Val => Val) = 

    12   (v:Val) => Seq(f1(Empty), f2(v))

    13 def F_SEQ_Empty2(f1: Val => Val, f2: Val => Val) = 

    14   (v:Val) => Seq(f1(v), f2(Empty))

    15 def F_ERROR(v: Val): Val = throw new Exception("error")

    16 

    17 // simplification of regular expressions returning also a

    18 // rectification function; no simplification under STAR 

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

    20   case ALT(r1, r2) => {

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

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

    23     (r1s, r2s) match {

    24       case (ZERO, _) => (r2s, F_RIGHT(f2s))

    25       case (_, ZERO) => (r1s, F_LEFT(f1s))

    26       case _ => if (r1s == r2s) (r1s, F_LEFT(f1s))

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

    28     }

    29   }

    30   case SEQ(r1, r2) => {

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

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

    33     (r1s, r2s) match {

    34       case (ZERO, _) => (ZERO, F_ERROR)

    35       case (_, ZERO) => (ZERO, F_ERROR)

    36       case (ONE, _) => (r2s, F_SEQ_Empty1(f1s, f2s))

    37       case (_, ONE) => (r1s, F_SEQ_Empty2(f1s, f2s))

    38       case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s))

    39     }

    40   }

    41   case r => (r, F_ID)

    42 }