Scala: Есть ли лучший способ оценить дерево выражений?

Question

Я изучаю Скалу, работая над упражнениями из книги «Скала для нетерпимого». Один вопрос спрашивает:

/** 
    * 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 
    * 
    */ 

Мое решение заключается в следующем. Вы можете улучшить его? В частности, мне интересно, есть ли способ прямого сопоставления с функциями вместо имен методов. Например, если я мог бы написать что-то вроде следующего мысленного заявления

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

тогда я мог бы объединить + и - случаев. То же самое касается * и /.

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 
} 

Тестовый пример:

"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

Некоторые мысли:

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

Вы можете определить op быть функцией от List[Int] к Int. Таким образом, eval либо вернет значение в случае, если дерево является листом, либо op(children map eval) в противном случае. Обратите внимание, что вы можете передать toString в качестве аргумента конструктора в ExprTreeNode, потому что функции не имеют хорошего строкового представления.

Это решение будет выглядеть следующим образом:

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) 
    } 
} 

Существует поймать, однако: Вы не имеют статические гарантии, что аргумент функции op имеет такой же длины, как и children. Чтобы получить статическую безопасность, вы можете использовать только унарные и двоичные деревья (с op: (Int, Int) => Int и op: Int => Int соответственно), ур использует бесформенную, в частности Sized, которая кодирует длину списка (если статически известна) в системе типов.

Answer 3

Возможно, что упрощает eval Функция.

Я использую пользовательские типы (ExprOp) для представления операций (+, -, * и т.д.) Этот код является неполным, но достаточно, чтобы передать идею, что ExprOp может быть полезно :)

//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