Scala albero metodo

Question

ricorsivo volte dato la seguente definizione per una (non binario) albero:

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

ho scritto il seguente piega metodo:

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

che può essere ben utilizzato per (tra le altre cose) questo mappa metodo:

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

Domanda: qualcuno può aiutarmi a scrivere una versione ricorsiva di coda della precedente piega?

Answer 1

Credo che tu abbia bisogno di una pila per fare un tale attraversamento, proprio come nella programmazione imperativa, non ci sarebbe alcun modo naturale di scriverlo senza un metodo ricorsivo. Naturalmente, puoi sempre gestire lo stack tu stesso, che lo sposta nell'heap e impedisce lo stack overflow. Ecco un esempio:

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, cs, nextChild :: others) :: tail => 
     go(
     StackFrame(nextChild.value, Nil, nextChild.children) :: 
     StackFrame(v, cs, others) :: 
     tail) 
    case Nil => sys.error("Should not go there") 
    } 

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

Nota: ho fatto Node covariante, non è strettamente necessario, ma se non lo è, dovrete essere esplicito nel tipo di pochi Nil (ad es Sostituire con List[X]()) in qualche posto.

go chiaramente coda ricorsiva, ma solo perché gestisce lo stack stesso.

È possibile trovare una tecnica più di principio e sistematica (ma non facile da afferrare all'inizio) basata su continuazioni e trampolini, in this nice blog post.