1

这是楼梯书上的一个 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")

这可行但很乏味（我正在使用的实际类有几个案例子类）。另外，我可能需要几个类似的转换。有没有更好的选择（可能使用高阶函数）？

4

1 回答 1

2

所以你的版本renameVar必须知道两个不同的事情：它必须知道如何递归树，它必须知道如何重命名变量。

一种解决方案可能是将这两个问题分开。您可以使用访问者设计模式让每个类控制它如何进行递归；visit 方法只关心如何遍历树。当它遍历时，它可以通过一个处理实际工作的函数（在你的情况下重命名一个变量）。

这是一个简单的实现，它传递一个转换函数（操作Expr并返回一个Expr）。它使用 a 的事实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）即可工作。

于 2012-04-25T05:04:16.667 回答