假设我有一个这样的树数据结构:
trait Node { val name: String }
case class BranchNode(name: String, children: List[Node]) extends Node
case class LeafNode(name: String) extends Node
假设我还有一个映射叶子的函数:
def mapLeaves(root: Node, f: LeafNode => LeafNode): Node = root match {
case ln: LeafNode => f(ln)
case bn: BranchNode => BranchNode(bn.name, bn.children.map(ch => mapLeaves(ch, f)))
}
现在我试图使这个函数尾递归,但很难弄清楚如何做到这一点。我已经阅读了这个answer但仍然不知道使二进制树解决方案适用于多路树。
你会如何重写mapLeaves
以使其尾递归?
“调用堆栈”和“递归”仅仅是流行的设计模式,后来被合并到大多数编程语言中(因此变得大部分是“不可见的”)。没有什么可以阻止您使用堆数据结构重新实现这两者。所以,这是“显而易见的”1960年代TAOCP复古风格的解决方案:
trait Node { val name: String }
case class BranchNode(name: String, children: List[Node]) extends Node
case class LeafNode(name: String) extends Node
def mapLeaves(root: Node, f: LeafNode => LeafNode): Node = {
case class Frame(name: String, mapped: List[Node], todos: List[Node])
@annotation.tailrec
def step(stack: List[Frame]): Node = stack match {
// "return / pop a stack-frame"
case Frame(name, done, Nil) :: tail => {
val ret = BranchNode(name, done.reverse)
tail match {
case Nil => ret
case Frame(tn, td, tt) :: more => {
step(Frame(tn, ret :: td, tt) :: more)
}
}
}
case Frame(name, done, x :: xs) :: tail => x match {
// "recursion base"
case l @ LeafNode(_) => step(Frame(name, f(l) :: done, xs) :: tail)
// "recursive call"
case BranchNode(n, cs) => step(Frame(n, Nil, cs) :: Frame(name, done, xs) :: tail)
}
case Nil => throw new Error("shouldn't happen")
}
root match {
case l @ LeafNode(_) => f(l)
case b @ BranchNode(n, cs) => step(List(Frame(n, Nil, cs)))
}
}
尾递归step
函数采用带有“堆栈帧”的reified堆栈。 “堆栈帧”存储当前正在处理的分支节点的名称,已经处理的子节点的列表,以及稍后仍然必须处理的剩余节点的列表。这大致对应于递归mapLeaves
函数的实际堆栈帧。
有了这个数据结构,
Frame
对象,并返回最终结果,或者至少使stack
缩短一帧。Frame
添加到stack
的步骤f
)不会创建或删除任何帧一旦人们理解了通常不可见的堆栈帧是如何明确表示的,那么翻译就很简单,而且大多是机械的。
例:
val example = BranchNode("x", List(
BranchNode("y", List(
LeafNode("a"),
LeafNode("b")
)),
BranchNode("z", List(
LeafNode("c"),
BranchNode("v", List(
LeafNode("d"),
LeafNode("e")
))
))
))
println(mapLeaves(example, { case LeafNode(n) => LeafNode(n.toUpperCase) }))
输出(缩进):
BranchNode(x,List(
BranchNode(y,List(
LeafNode(A),
LeafNode(B)
)),
BranchNode(z, List(
LeafNode(C),
BranchNode(v,List(
LeafNode(D),
LeafNode(E)
))
))
))
使用名为trampoline的技术实现它可能更容易。如果你使用它,你将能够使用两个调用自身进行相互递归的函数(使用tailrec
,你只能使用一个函数)。与tailrec
类似,此递归将转换为普通循环。
蹦床在scala.util.control.TailCalls
的scala标准库中实现。
import scala.util.control.TailCalls.{TailRec, done, tailcall}
def mapLeaves(root: Node, f: LeafNode => LeafNode): Node = {
//two inner functions doing mutual recursion
//iterates recursively over children of node
def iterate(nodes: List[Node]): TailRec[List[Node]] = {
nodes match {
case x :: xs => tailcall(deepMap(x)) //it calls with mutual recursion deepMap which maps over children of node
.flatMap(node => iterate(xs).map(node :: _)) //you can flat map over TailRec
case Nil => done(Nil)
}
}
//recursively visits all branches
def deepMap(node: Node): TailRec[Node] = {
node match {
case ln: LeafNode => done(f(ln))
case bn: BranchNode => tailcall(iterate(bn.children))
.map(BranchNode(bn.name, _)) //calls mutually iterate
}
}
deepMap(root).result //unwrap result to plain node
}
你可以使用TailCalls
的Eval
或Cats
的Trampoline
代替scalaz
。
有了这个实现功能,没有问题:
def build(counter: Int): Node = {
if (counter > 0) {
BranchNode("branch", List(build(counter-1)))
} else {
LeafNode("leaf")
}
}
val root = build(4000)
mapLeaves(root, x => x.copy(name = x.name.reverse)) // no problems
当我使用您的实现运行该示例时,它会导致java.lang.StackOverflowError
正常运行。