케이스 트리 변환

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

이 작업은하지만 지루합니다 (실제 클래스는 몇 가지 사례 하위 클래스가 있습니다). 또한 몇 가지 유사한 변형이 필요할 수 있습니다. 거기에 더 나은 대안 (가능성이 높은 순서 기능을 사용하여)?

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과 같은 다른 변환 함수).