Match tree simplification (http://www.scala-lang.org/docu/files/ScalaTutorial.pdf)

app.sc

abstract class Tree

case class Sum(l: Tree, r: Tree) extends Tree {
  override def toString(): String = "(" + l + " + " + r + ")"
}

case class Var(n: String) extends Tree {
  override def toString(): String = n
}

case class Const(v: Int) extends Tree {
  override def toString(): String = v.toString
}


type Environment = String => Int


def eval(t: Tree, env: Environment): Int = t match {
  case Sum(l, r) => eval(l, env) + eval(r, env)
  case Var(n) => env(n)
  case Const(v) => v
}


def derive(t: Tree, v: String): Tree = t match {
  case Sum(l, r) => Sum(derive(l, v), derive(r, v))
  case Var(n) if v == n => Const(1)
  case _ => Const(0)
}


def simplify(t: Tree): Tree = t match {
  case Sum(l: Const, r: Const) => Const(eval(t, { case _ => 0 }))

  case Sum(l: Const, r) if l == Const(0) => simplify(r)

  case Sum(l, r: Const) if r == Const(0) => simplify(l)

  case Sum(l: Sum, r: Sum) =>
    val t1: Tree = Sum(simplify(l), simplify(r))
    t1 match {
      case Sum(l1: Const, r1: Const) => simplify(t1)
      case _ => t1
    }

  case Sum(l: Sum, r) => Sum(simplify(l), r)

  case Sum(l, r: Sum) => Sum(l, simplify(r))

  case _ => t
}

val exp: Tree = Sum(Sum(Var("x"), Var("x")), Sum(Const(7), Var("y")))

simplify(exp)

simplify(derive(exp, "x"))

simplify(derive(exp, "y"))

results

defined class Tree

defined class Sum



defined class Var



defined class Const




defined type alias Environment


eval: eval[](val t: Tree,val env: Environment) => Int






derive: derive[](val t: Tree,val v: String) => Tree






simplify: simplify[](val t: Tree) => Tree




















exp: Tree = ((x + x) + (7 + y))

res0: Tree = ((x + x) + (7 + y))

res1: Tree = 2

res2: Tree = 1