如何使树映射尾递归? [英] How to make tree mapping tail-recursive?

问题描述

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

Suppose I have a tree data structure like this:

trait Node { val name: String }
case class BranchNode(name: String, children: List[Node]) extends Node
case class LeafNode(name: String) extends Node

假设我还有一个映射到叶子上的函数:

Suppose also I've got a function to map over leaves:

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

现在，我正在尝试使此功能 tail-recursive ，但是很难弄清楚该怎么做.我已经阅读了 answer ，但仍然不知道该采用哪种二叉树解决方案为多路树工作.

Now I am trying to make this function tail-recursive but having a hard time to figure out how to do it. I've read this answer but still don't know to make that binary tree solution work for a multiway tree.

您将如何重写mapLeaves以使其尾部递归?

How would you rewrite mapLeaves to make it tail-recursive?

推荐答案

调用栈"和递归"只是流行的设计模式，后来被并入大多数编程语言中(因此大部分变为不可见").没有什么可以阻止您使用堆数据结构来重新实现两者.因此，这是显而易见的" 1960年代的TAOCP复古风格的解决方案:

"Call stack" and "recursion" are merely popular design patterns that later got incorporated into most programming languages (and thus became mostly "invisible"). There is nothing that prevents you from reimplementing both with heap data structures. So, here is "the obvious" 1960's TAOCP retro-style solution:

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函数采用带有堆栈框架"的经过优化的堆栈. 堆栈帧"存储当前正在处理的分支节点的名称，已处理的子节点的列表以及以后仍必须处理的其余节点的列表.这大致对应于递归mapLeaves函数的实际堆栈框架.

The tail-recursive step function takes a reified stack with "stack frames". A "stack frame" stores the name of the branch node that is currently being processed, a list of child nodes that have already been processed, and the list of the remaining nodes that still must be processed later. This roughly corresponds to an actual stack frame of your recursive mapLeaves function.

有了这种数据结构，

从递归调用返回
• 对应于解构Frame对象，并返回最终结果，或者至少使stack缩短一帧.
• 递归调用对应于将Frame附加到stack
的步骤
• 基本情况(在叶子上调用f)不会创建或删除任何框架

• returning from recursive calls corresponds to deconstructing a Frame object, and either returning the final result, or at least making the stack one frame shorter.
• recursive calls correspond to a step that prepends a Frame to the stack
• base case (invoking f on leaves) does not create or remove any frames

一旦理解了通常不可见的堆栈框架是如何被明确表示的，那么翻译就很简单，而且大多是机械的.

Once one understands how the usually invisible stack frames are represented explicitly, the translation is straightforward and mostly mechanical.

示例:

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

这篇关于如何使树映射尾递归?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！