案例树转换

Question

这是一本来自楼梯书的Expr课程。

abstract class Expr 
case class Var(name: String) extends Expr 
case class Number(num: Double) extends Expr 
case class UnOp(operator: String, arg: Expr) extends Expr 
case class BinOp(operator: String, left: Expr, right: Expr) extends Expr 

现在，我想要一个函数来重命名表达式中的变量。这是我的第一次尝试。

def renameVar(expr: Expr, varName: String, newName: String): Expr = expr match { 
    case Var(name) if name == varName => Var(newName) 
    case Number(_) => expr 
    case UnOp(operator, arg) => UnOp(operator, renameVar(arg, varName, newName)) 
    case BinOp(operator, left, right) => BinOp(operator, renameVar(left, varName, newName), renameVar(right, varName, newName)) 
} 

val anExpr = BinOp("+", Number(1), Var("x")) 
val anExpr2 = renameVar(anExpr, "x", "y") 

这很有效，但很繁琐（我正在使用的实际类有几个case子类）。另外，我可能需要几个类似的转换。是否有更好的选择（可能使用更高阶的函数）？

Answer 1

所以你的renameVar版本有了解两回事：它必须知道如何递归树，它必须知道如何重命名变量。

一个解决方案可能是将这两个问题分开。您可以使用visitor design pattern为每个类控制递归如何执行;访问方法只关心如何遍历树。当它遍历时，它可以通过一个处理实际工作的函数（在你的案例中重命名一个变量）。

下面是一个简单的实现，通过变换函数（即上Expr操作，并且返回一个Expr）。它使用PartialFunction的事实允许您对树中的表达进行模式匹配以进行操作。任何未被案例覆盖的表达式都会回到正常递归（如由doVisit指定）。

根据各种不同的任务，你可能需要有一个更复杂的访问方法。但是，这应该给你方向的一个想法：

// Class Hierarchy 
abstract class Expr { 
    def visit(f: PartialFunction[Expr, Expr]): Expr = if (f.isDefinedAt(this)) f(this) else doVisit(f) 
    protected def doVisit(f: PartialFunction[Expr, Expr]): Expr 
} 
case class Var(name: String) extends Expr { 
    protected def doVisit(f: PartialFunction[Expr, Expr]) = this 
} 
case class Number(num: Double) extends Expr { 
    protected def doVisit(f: PartialFunction[Expr, Expr]) = this 
} 
case class UnOp(operator: String, arg: Expr) extends Expr { 
    protected def doVisit(f: PartialFunction[Expr, Expr]) = UnOp(operator, arg.visit(f)) 
} 
case class BinOp(operator: String, left: Expr, right: Expr) extends Expr { 
    protected def doVisit(f: PartialFunction[Expr, Expr]) = BinOp(operator, left.visit(f), right.visit(f)) 
} 

// Transformation Functions 
def renameVar(expr: Expr, varName: String, newName: String): Expr = { 
    expr.visit { case Var(`varName`) => Var(newName) } 
} 

现在你可以引入一个新的类，像TernaryOp(String, Expr, Expr, Expr)，以类似的方式定义其doVisit方法，而不会导致你不必修改renameVar工作（或任何其他转换函数，如renameVar）。