Il seguente numero blog article mostra come in F # foldBack
è possibile eseguire la ricorsione in coda usando lo stile di passaggio di continuazione.È possibile utilizzare le continuazioni per rendere ricorsiva la coda di foldRight?
In Scala questo significherebbe che:
def foldBack[T,U](l: List[T], acc: U)(f: (T, U) => U): U = {
l match {
case x :: xs => f(x, foldBack(xs, acc)(f))
case Nil => acc
}
}
può essere fatto la coda ricorsiva in questo modo:
def foldCont[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
@annotation.tailrec
def loop(l: List[T], k: (U) => U): U = {
l match {
case x :: xs => loop(xs, (racc => k(f(x, racc))))
case Nil => k(acc)
}
}
loop(list, u => u)
}
Purtroppo, ho ancora un overflow dello stack per lunghi elenchi. il ciclo è ricorsivo e ottimizzato per la coda, ma suppongo che l'accumulo di stack venga spostato nelle chiamate di continuazione.
Perché questo non è un problema con F #? E c'è un modo per aggirare questo problema con Scala?
Edit: qui un codice che indica la profondità della pila:
def showDepth(s: Any) {
println(s.toString + ": " + (new Exception).getStackTrace.size)
}
def foldCont[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
@annotation.tailrec
def loop(l: List[T], k: (U) => U): U = {
showDepth("loop")
l match {
case x :: xs => loop(xs, (racc => { showDepth("k"); k(f(x, racc)) }))
case Nil => k(acc)
}
}
loop(list, u => u)
}
foldCont(List.fill(10)(1), 0)(_ + _)
Questo stampa:
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
k: 51
k: 52
k: 53
k: 54
k: 55
k: 56
k: 57
k: 58
k: 59
k: 60
res2: Int = 10
Non ha senso. Hai un semplice caso di test? –
@ DanielC.Sobral, vedere il codice che ho aggiunto e che stampa. – huynhjl