Scala : Is there a better way to evaluate an expression tree?

Question

I'm learning Scala by working the exercises from the book "Scala for the Impatient". One question asks:

/**
   * Q8: Extends the tree in the preceding exercise so that each non-leaf node stores an operator in addition to
   * the child nodes. Then write a function `eval` that computes the value. For example, the tree
   *
   *         +
   *    *    2    -
   *  3   8      5
   *
   * has a value (3 * 8) + 2 + (-5) = 21
   *
   */

My solution is as follows. Can you improve on it? In particular, I'm wondering if there's a way to directly match against the functions instead of the method names. For example, if I could write something like the following imaginary statement

case ExprTreeNode(f, children @ _*) if (f == Int.+ || f == Int.-) => children.foldLeft(0) { (acc, elem) => eval(elem) f acc }

then I could combine the + and - cases. Same goes for * and /.

sealed abstract class ExpressionTree
case class ExprTreeLeaf(value: Int) extends ExpressionTree
case class ExprTreeNode(op: String, children: ExpressionTree*) extends ExpressionTree

def eval(expr: ExpressionTree): Int = expr match {
  case ExprTreeNode("+", children @ _*) => children.foldLeft(0) { _ + eval(_) }
  case ExprTreeNode("*", children @ _*) => children.foldLeft(1) { _ * eval(_) }
  case ExprTreeNode("/", children @ _*) => children.foldLeft(1) { (acc, elem) => eval(elem) / acc }
  case ExprTreeNode("-", child) => eval(child).unary_- // Order matters here, 'children @ _*' would match 1 child
  case ExprTreeNode("-", children @ _*) => children.foldLeft(0) { (acc, elem) => eval(elem) - acc }
  case leaf: ExprTreeLeaf => leaf.value
}

Test case:

"Method eval" should "evaluate an expression tree" in {
  val expr = ExprTreeNode("+", ExprTreeNode("*", ExprTreeLeaf(3), ExprTreeLeaf(8)), ExprTreeLeaf(2), ExprTreeNode("-", ExprTreeLeaf(5)))

  eval(expr) should be(21)
}

Answer 1

Some thoughts:

object TestApp extends App{

  sealed abstract class Tree
  case class Leaf(value: Int) extends Tree
  case class Node(op: String, children: Tree*) extends Tree



  //change to map and reduce to remove need for initial value
  def evalReduce(expr: Tree): Int = expr match {
    case Node("-", child) => evalReduce(child).unary_- // Order matters here, 'children @ _*' would match 1 child
    case Node("+", children @ _*) => children.map(evalReduce).reduceLeft(_+_)
    case Node("*", children @ _*) => children.map(evalReduce).reduceLeft(_*_)
    case Node("/", children @ _*) => children.map(evalReduce).reduceLeft(_/_)
    case Node("-", children @ _*) => children.map(evalReduce).reduceLeft(_-_)
    case leaf: Leaf => leaf.value
  }

  // long to declare plus/minus/divide/multiply functions
  // not much prettier/simpler than evalReduce
  val stringToFunction = Map[String,(Int,Int)=>Int](
    "+"->{(i:Int,j:Int)=>i+j},
    "*"->{(i:Int,j:Int)=>i*j},
    "/"->{(i:Int,j:Int)=>i/j},
    "-"->{(i:Int,j:Int)=>i-j}
  )

  def evalCasesUnified(expr: Tree): Int = expr match {
    case Node("-", child) => evalCasesUnified(child).unary_- // Order matters here, 'children @ _*' would match 1 child
    case Node(s, children @ _*) => children.map(evalCasesUnified).reduceLeft(stringToFunction(s))
    case leaf: Leaf => leaf.value
  }


  sealed abstract class TreeFunctional
  case class LeafFunctional(value: Int) extends TreeFunctional
  case class NodeUnaryFunctional(op: Int=>Int, child: TreeFunctional) extends TreeFunctional
  case class NodeFunctional(op: (Int,Int)=>Int, children: TreeFunctional*) extends TreeFunctional

  def evalFunctional(expr: TreeFunctional): Int = expr match {
    case NodeUnaryFunctional(f, child) => f(evalFunctional(child)) 
    case NodeFunctional(f, children @ _*) => children.map(evalFunctional).reduceLeft(f)
    case leaf: LeafFunctional => leaf.value
  }
  val expr = Node("+", Node("*", Leaf(3), Leaf(8)), Leaf(2), Node("-", Leaf(5)))
  val exprFunctional = NodeFunctional({_+_}, NodeFunctional({_*_}, LeafFunctional(3), LeafFunctional(8)), LeafFunctional(2), NodeUnaryFunctional({-_}, LeafFunctional(5)))

  def plus(i:Int,j:Int):Int = {i+j}
  def minus(i:Int,j:Int):Int = {i-j}
  def minusUnary(i:Int):Int = -i
  def multiply(i:Int,j:Int):Int = {i*j}
  def divide(i:Int,j:Int):Int = {i/j}

  val exprFunctionalNicer = NodeFunctional(plus, NodeFunctional(multiply, LeafFunctional(3), LeafFunctional(8)), LeafFunctional(2), NodeUnaryFunctional(minusUnary, LeafFunctional(5)))

  //but then you could create a case class for each function

  sealed abstract class TreeNamed
  case class Value(value: Int) extends TreeNamed

  abstract class UnaryNode() extends TreeNamed {
    val child: TreeNamed
    def op: Int=>Int
  }
  case class MinusUnary(child:TreeNamed) extends UnaryNode{
    def op = {-_}
  }

  abstract class MultinaryNode() extends TreeNamed {
    val children: Seq[TreeNamed]
    def op: (Int,Int)=>Int
  }

  case class Plus(children:TreeNamed*) extends MultinaryNode{
    def op = {_+_}
  }
  case class Minus(children:TreeNamed*) extends MultinaryNode{
    def op = {_-_}
  }
  case class Multiply(children:TreeNamed*) extends MultinaryNode{
    def op = {_*_}
  }
  case class Divide(children:TreeNamed*) extends MultinaryNode{
    def op = {_/_}
  }

  val exprNamed = Plus(Multiply(Value(3), Value(8)), Value(2), MinusUnary(Value(5)))

  def evalNamed(expr: TreeNamed): Int = expr match {
    case u:UnaryNode => u.op(evalNamed(u.child))
    case m:MultinaryNode => m.children.map(evalNamed).reduceLeft(m.op)
    case leaf: Value => leaf.value
  }


  println(evalReduce(expr))
  println(evalCasesUnified(expr))
  println(evalFunctional(exprFunctional))
  println(evalFunctional(exprFunctionalNicer))
  println(evalNamed(exprNamed))
}

Answer 2

You can define op to be a function from List[Int] to Int. This way, eval will either return the value in case the tree is a leaf, or op(children map eval) otherwise. Note that you may want to pass toString as a constructor argument to ExprTreeNode, because functions do not have a nice string representation.

This solution would look as follows:

sealed abstract class ExpressionTree

case class ExprTreeLeaf(value: Int) extends ExpressionTree

case class ExprTreeNode(op: List[Int] => Int, children: List[ExpressionTree]) extends ExpressionTree

object ExprTreeNode {
  // convenience method
  def apply(op: List[Int] => Int, children: ExpressionTree*) = new ExprTreeNode(op, children.toList)
}

object ExpressionTree {

  val Plus: List[Int] => Int = a => a.sum
  val UnaryMinus: List[Int] => Int = {
    case List(a: Int) => -a
  }
  val Times: List[Int] => Int = a => a.product

  def main(args: Array[String]) {
    val expr = ExprTreeNode(Plus, ExprTreeNode(Times, ExprTreeLeaf(3), ExprTreeLeaf(8)), ExprTreeLeaf(2), ExprTreeNode(UnaryMinus, ExprTreeLeaf(5)))
    println(eval(expr))
  }

  def eval(expr: ExpressionTree): Int = expr match {
    case ExprTreeLeaf(value) => value
    case ExprTreeNode(op, children) => op(children map eval)
  }
}

There is a catch however: You do not have static guarantees that the argument to the function op is of the same length as children. To get static safety, you could either only allow unary and binary trees (with op: (Int, Int) => Int and op: Int => Int respectively), ur utilize shapeless, specifically Sized, which encodes the length of a list (if statically known) in the type system.

Answer 3

Here is a possibility that simplifies the eval function.

I use custom types (ExprOp) to represent the operations (+, -, *, etc.) This code is incomplete, but it is enough to convey the idea that ExprOp can be useful :)

//here is the expression tree :
trait Expr
case class Value(value:Int) extends Expr
case class Op(op : ExprOp, left : Expr, right : Expr) extends Expr

//here are the operations :
trait ExprOp{
    def apply(lhs:Int, rhs:Int) : Int
}
object Add extends ExprOp{
    def apply(lhs:Int, rhs:Int) : Int = lhs + rhs
}
object Mul extends ExprOp{
    def apply(lhs:Int, rhs:Int) : Int = lhs * rhs
} //... Create object Div, Sub in the same way

// here is the eval function 
// notice how simple it is ! 

def eval(e:Expr):Int = e match {
    case Value(n) => n
    case Op(op, lhs, rhs) => op(eval(lhs), eval(rhs))
}  //nothing more needed