Как сделать отображение дерева хвост-рекурсивным? - PullRequest
Новая
       66

Как сделать отображение дерева хвост-рекурсивным?

7 голосов
/ 07 марта 2019

Предположим, у меня есть древовидная структура данных: 

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, чтобы сделать его хвост-рекурсивным?

Ответы [ 2 ]

5 голосов
/ 07 марта 2019

Это может быть проще реализовать с помощью техники под названием батут . Если вы воспользуетесь им, вы сможете использовать две функции, вызывающие себя для выполнения взаимной рекурсии (с tailrec вы ограничены одной функцией). Аналогично tailrec эта рекурсия будет преобразована в простой цикл.

Батуты реализованы в стандартной библиотеке Scala в scala.util.control.TailCalls. 

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, как и ожидалось.

5 голосов
/ 07 марта 2019

«Стек вызовов» и «рекурсия» - это просто популярные шаблоны проектирования, которые впоследствии были включены в большинство языков программирования (и, таким образом, стали в основном «невидимыми»). Ничто не мешает вам переопределить обе структуры данных кучи. Итак, вот «очевидное» решение в стиле ретро TAOCP 1960-х годов: 

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.

С этой структурой данных,

  • возврат из рекурсивных вызовов соответствует деконструкции 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)
    ))
  ))
))
...