def F_ID(v: Val): Val = v

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

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

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

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

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

}

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

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

}

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

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

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

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

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

// simplification of regular expressions returning also a

// rectification function; no simplification under STAR 

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

  case ALT(r1, r2) => {

    val (r1s, f1s) = simp(r1)

    val (r2s, f2s) = simp(r2)

    (r1s, r2s) match {

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

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

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

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

    }

  }

  case SEQ(r1, r2) => {

    val (r1s, f1s) = simp(r1)

    val (r2s, f2s) = simp(r2)

    (r1s, r2s) match {

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

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

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

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

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

    }

  }

  case r => (r, F_ID)

}