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.
Molto chiaro (ed efficace), ho anche azzardato nel post del blog e relativo [carta] (http://blog.higher-order.com/assets/trampolines.pdf). Affascinante ma difficile, accumulatore di steroidi ... Quindi non sto sottovalutando il problema, ma lasciatemi dire che dal punto di vista degli "utenti" sarebbe un sogno scrivere un one-liner ricorsivo senza coda e lasciare che il compilatore trovi la migliore soluzione per l'ottimizzazione. – user2364174
Il codice può essere leggermente ottimizzato sostituendo cs a cs.reverse e csUp: + piegato a piegato :: csUp – user2364174
Non csUp: + piegato O (n)? –