Scala树递归折叠方法

发布时间：2020-12-16 08:52:16 所属栏目：安全来源：网络整理

导读：给定(非二进制)树的以下定义： sealed trait Tree[+A]case class Node[A](value: A,children: List[Node[A]]) extends Tree[A]object Tree {...} 我写了以下折叠方法： def fold[A,B](t: Node[A])(f: A ? B)(g: (B,List[B]) ? B): B = g(f(t.value),t.childr

给定(非二进制)树的以下定义：

sealed trait Tree[+A]
case class Node[A](value: A,children: List[Node[A]]) extends Tree[A]
object Tree {...}

我写了以下折叠方法：

def fold[A,B](t: Node[A])(f: A ? B)(g: (B,List[B]) ? B): B =
  g(f(t.value),t.children map (fold(_)(f)(g)))

这可以很好地用于(除其他外)这个map方法：

def map[A,B](t: Node[A])(f: A ? B): Node[B] =
  fold(t)(x ? Node(f(x),List()))((x,y) ? Node(x.value,y))

问题：有人可以帮助我如何编写上面的折叠尾部递归版本吗？

解决方法

我相信你需要一个堆栈来进行这样的遍历,就像在命令式编程中一样,如果没有递归方法,就没有自然的方法来编写它.当然,您可以自己管理堆栈,将堆栈移动到堆中,并防止堆栈溢出.这是一个例子：

sealed trait Tree[+A]
case class Node[+A](value: A,children: List[Node[A]]) extends Tree[A]

case class StackFrame[+A,+B](
  value: A,computedChildren: List[B],remainingChildren: List[Node[A]])

def fold[A,B](t: Node[A])(f: A => B)(g: (B,List[B]) => B) : B = {

  def go(stack: List[StackFrame[A,B]]) : B = stack match {
    case StackFrame(v,cs,Nil) :: tail => 
      val folded = g(f(v),cs.reverse)
      tail match {
        case Nil => folded
        case StackFrame(vUp,csUp,remUp) :: rest => 
          go(StackFrame(vUp,folded::csUp,remUp)::rest)
      }
    case StackFrame(v,nextChild :: others) :: tail =>
      go(
        StackFrame(nextChild.value,Nil,nextChild.children) ::
        StackFrame(v,others) :: 
        tail)
    case Nil => sys.error("Should not go there")
  }

  go(StackFrame(t.value,t.children) :: Nil)    
}

注意：我创建了Node协变,并非严格必要,但如果不是,则需要在某些地方明确表示几个Nil的类型(例如,由List [X]()替换).

明确尾部递归,但仅仅因为它管理堆栈本身.

在this nice blog post中,您可能会发现基于延续和蹦床的更具原则性和系统性的技术(但最初并不容易掌握).

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!