案例樹轉換

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）。