CODEWITHSUNDEEP
scalapattern-matching
Mik378
Mik378

Reputation: 22191

How to achieve the expression simplification with distributivity rule in Scala?

I want to write a scala program simplifying this mathematical expression using distributivity rule:

a*b+a*c = a(b+c)

I quickly wrote the following code in order to solve this example:

object Test {

  sealed abstract class Expr

  case class Var(name: String) extends Expr

  case class BinOp(operator: String, left: Expr, right: Expr) extends Expr


  def main(args: Array[String]) {
    val expr = BinOp("+", BinOp("*", Var("a"), Var("b")), BinOp("*", Var("a"), Var("c")))
    println(simplify(expr)) //outputs "a(b + c)"
  }

  def simplify(expr: Expr) : String = expr match {
    case BinOp("+", BinOp("*", Var(x), Var(a)), BinOp("*", Var(y), Var(b))) if (x == y) => "" + x + "*(" + a + " + " + b + ")"
    case _ => "" //no matter for the test since I test the first case statically
  }

}

Is there a better way to achieve this?

What is the best way to manage the order of operand without duplicating cases for each combination (would be ugly...)? Indeed, what about these expressions:

a*b+a*c = a(b+c)

a*b+c*a = a(b+c)

b*a+a*c = a(b+c)

b*a+c*a = a(b+c)

Upvotes: 1

Views: 297

Answers (1)

yakamoto
yakamoto

Reputation: 50

If Expr keeps commutative law, it must be

def simplify(expr: Expr) : String = expr match {
  case expr @ BinOp("+", BinOp("*", Var(x), Var(a)), BinOp("*", Var(y), Var(b))) => {
    def another(that: String) = {
      Seq((x, a), (a, x)) find (_._1 == that) map (_._2)
    }

    val byY = another(y).map(z => BinOp("+", Var(y), BinOp("*", Var(z), Var(b)))) // combine by y
    val byB = another(b).map(z => BinOp("+", Var(b), BinOp("*", Var(z), Var(y)))) // combine by b
    (byY orElse byB getOrElse expr).toString
  }
  case _ => "" //no matter for the test since I test the first case statically
}

byY and byB have the same structure. This is not the best, you maybe reuse some piece of code. :P

Upvotes: 1

Related Questions