如何使树映射尾递归？

Question

假设我有一个像这样的树数据结构：

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

现在我正在尝试使这个函数尾递归但是很难弄清楚如何去做。我读过这个但仍然不知道如何使二叉树解决方案适用于多路树。

您将如何重写 mapLeaves 使其成为尾递归？

Answer 1

"Call stack" 和 "recursion" 只是流行的设计模式，后来被纳入大多数编程语言（因此主要成为 "invisible"）。没有什么可以阻止您使用堆数据结构重新实现两者。所以，这里是"the obvious"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 函数采用 "stack frames" 的具体化堆栈。一个"stack frame"中存放的是当前正在处理的分支节点名称，已经处理过的子节点列表，以及后面还需要处理的剩余节点列表。这大致对应于递归 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)
    ))
  ))
))

Answer 2

使用称为 trampoline 的技术可能更容易实现它。如果你使用它，你将能够使用两个调用自身的函数来进行相互递归（使用 tailrec，你只能使用一个函数）。与 tailrec 类似，此递归将被 t运行形成普通循环。

Trampolines 在 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
}

您还可以使用 Cats 中的 Eval 或 scalaz 中的 Trampoline。

而不是 TailCalls

使用该实现函数可以正常工作：

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.WhosebugError。

如何使树映射尾递归？

How to make tree mapping tail-recursive?

tree

recursion

functional-programming

scala

tail-recursion