我有一個Expr值在Scala中有兩個子Expr，我該如何執行這個在尾部位置？

Question

我有這樣定義Expr的類的一堆：

sealed trait BoolExpr 
sealed trait Value[T] { 
    def get: T 
} 

final case class AndExpr(left: Expr, right: Expr) extends BoolExpr 
final case class EqualsExpr[T](value: Value[T], expectedValue: T) extends BoolExpr 

後，我構造的整個BoolExpr值，我將通過使用一個功能像這樣的執行它：

def exec(expr: BoolExpr) = { 
    expr match { 
    case EqualsExpr(value, expectedValue) => value.get == expectedValue 
    case AndExpr(left: Expr, right: Expr) => exec(left) && exec(right) 
    } 
} 

這是不夠好，因爲這是一個正常的遞歸。

我打算通過使用蹦牀來重構exec函數。

使用蹦牀要求每次此函數調用別的東西時，調用應該在尾部位置以便在蹦牀中變形。

但我找不到將exec(left) && exec(right)零件改寫成尾部調用樣式的方法。

有沒有一種方法可以做到這一點？

Answer 1

你在蹦牀的道路上。看看Cats或斯卡拉斯的蹦牀實施（其基於Free Monad）。或者您可以在scala.util.control.TailCalls包中使用vanilla Scala。由於所有這些設計都是單子，你可以做到以下幾點：

import util.control.TailCalls._ 

def exec(expr: BoolExpr) = expr match{ 
    case EqalsExpr(value, expectedValue) => done(value.get == expectedValue) 
    case AndExpr(left, right) => exec(left).flatMap{ 
    l => exec(right).map(l && _) 
    } 
} 

注意這裏來map和flatMap呼叫保持蹦牀的屬性和永遠不會導致堆棧爆炸。