2011-12-18 10 views
9

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 
+0

Non ha senso. Hai un semplice caso di test? –

+0

@ DanielC.Sobral, vedere il codice che ho aggiunto e che stampa. – huynhjl

risposta

4

Il problema è la funzione prosecuzione (racc => k(f(x, racc))) stessa. Dovrebbe essere ottimizzato per far funzionare tutto questo business, ma non lo è.

Scala non è in grado di effettuare ottimizzazioni tailcall per chiamate coda arbitrarie, solo per quelle che possono essere trasformate in loop (ad esempio quando la funzione chiama se stessa, non un'altra funzione).

+0

Questo è quello che ho indovinato. Si può fare qualcosa? Ti piace usare qualcosa come i trampolini? – huynhjl

+0

I trampolini probabilmente aiuteranno, ma penso che in questo caso "LeftFold" risolverebbe il problema con molto meno dolore. Se per qualche motivo devi assolutamente avere la semantica 'foldRight', puoi invertire la lista e chiamare' foldLeft' sul risultato. –

+1

Si scopre che in questo caso non è così doloroso vedere la mia risposta. – huynhjl

4

Perché questo non è un problema con F #?

F # ha tutte le chiamate di coda ottimizzate.

E c'è un modo per aggirare questo con Scala?

Si può fare TCO utilizzando altre tecniche come trampolini, ma si perde di interoperabilità perché cambia la convenzione di chiamata ed è ~ 10 × più lento. Questo è uno dei tre motivi per cui non uso Scala.

EDIT

I risultati dei benchmark indicano che trampolini di Scala sono un sacco più velocemente di quanto non fossero l'ultima volta che li ho testato. Inoltre, è interessante aggiungere benchmark equivalenti usando F # e per elenchi più grandi (perché non c'è motivo di fare CPS su piccoli elenchi!).

Per 1,000x in un elenco di 1.000 elemento sul mio netbook con un 1.67GHz N570 Intel Atom, ottengo:

List.fold  0.022s 
List.rev+fold 0.116s 
List.foldBack 0.047s 
foldContTC 0.334s 

Per 1x lista 1.000.000 elementi, ottengo:

List.fold  0.024s 
List.rev+fold 0.188s 
List.foldBack 0.054s 
foldContTC 0.570s 

Potresti anche essere interessato alle vecchie discussioni su questo nella lista-caml nel contesto della sostituzione delle funzioni di lista non ricorsive di OCaml con quelle ricorsive ottimizzate.

+3

Quali sono gli altri due motivi per cui non usi Scala? –

+3

@StephenSwensen: mancanza di tipi di valore e mancanza di inferenza di tipo. Si noti che la mancanza di chiamate di coda e tipi di valore è un problema con la JVM e non con Scala. Questi sono anche i motivi per cui ho scelto di sviluppare HLVM su LLVM piuttosto che sulla JVM. Il progetto di Geoff Reedy di portare Scala a LLVM ha il potenziale per risolvere entrambi questi problemi, il che sarebbe assolutamente fantastico. –

6

Jon, grazie per le vostre risposte. Sulla base dei tuoi commenti ho pensato di provare e usare il trampolino. Un po 'di ricerca mostra che Scala ha il supporto per la libreria di trampolini in TailCalls. Ecco cosa mi è venuta dopo un po 'di armeggiare intorno:

def foldContTC[T,U](list: List[T], acc: U)(f: (T, U) => U): U = { 
    import scala.util.control.TailCalls._ 
    @annotation.tailrec 
    def loop(l: List[T], k: (U) => TailRec[U]): TailRec[U] = { 
    l match { 
     case x :: xs => loop(xs, (racc => tailcall(k(f(x, racc))))) 
     case Nil => k(acc) 
    } 
    } 
    loop(list, u => done(u)).result 
} 

ero curioso di vedere come questo confronto alla soluzione senza il trampolino così come il foldLeft e foldRight implementazioni di default. Ecco il codice di riferimento e alcuni risultati:

val size = 1000 
val list = List.fill(size)(1) 
val warm = 10 
val n = 1000 
bench("foldContTC", warm, lots(n, foldContTC(list, 0)(_ + _))) 
bench("foldCont", warm, lots(n, foldCont(list, 0)(_ + _))) 
bench("foldRight", warm, lots(n, list.foldRight(0)(_ + _))) 
bench("foldLeft", warm, lots(n, list.foldLeft(0)(_ + _))) 
bench("foldLeft.reverse", warm, lots(n, list.reverse.foldLeft(0)(_ + _))) 

Gli orari sono:

foldContTC: warming... 
Elapsed: 0.094 
foldCont: warming... 
Elapsed: 0.060 
foldRight: warming... 
Elapsed: 0.160 
foldLeft: warming... 
Elapsed: 0.076 
foldLeft.reverse: warming... 
Elapsed: 0.155 

Sulla base di questo, sembrerebbe che trampolino è in realtà dando abbastanza buone prestazioni. Sospetto che la penalità in cima alla boxe/unboxing non sia poi così male.

Modifica: come suggerito dai commenti di Jon, qui ci sono i tempi sugli elementi 1M che confermano che le prestazioni si degradano con elenchi più grandi. Inoltre ho scoperto che l'attuazione List.foldLeft libreria non viene sovrascritto, quindi ho cronometrato con il seguente foldLeft2:

def foldLeft2[T,U](list: List[T], acc: U)(f: (T, U) => U): U = { 
    list match { 
    case x :: xs => foldLeft2(xs, f(x, acc))(f) 
    case Nil => acc 
    } 
} 

val size = 1000000 
val list = List.fill(size)(1) 
val warm = 10 
val n = 2 
bench("foldContTC", warm, lots(n, foldContTC(list, 0)(_ + _))) 
bench("foldLeft", warm, lots(n, list.foldLeft(0)(_ + _))) 
bench("foldLeft2", warm, lots(n, foldLeft2(list, 0)(_ + _))) 
bench("foldLeft.reverse", warm, lots(n, list.reverse.foldLeft(0)(_ + _))) 
bench("foldLeft2.reverse", warm, lots(n, foldLeft2(list.reverse, 0)(_ + _))) 

rendimenti:

foldContTC: warming... 
Elapsed: 0.801 
foldLeft: warming... 
Elapsed: 0.156 
foldLeft2: warming... 
Elapsed: 0.054 
foldLeft.reverse: warming... 
Elapsed: 0.808 
foldLeft2.reverse: warming... 
Elapsed: 0.221 

Così foldLeft2.reverse è il vincitore ...

+0

"prestazioni piuttosto buone". Infatti. Chiamerei quella performance sospettosamente buona! Forse l'implementazione del trampolino è abbastanza intelligente da rendersi conto che non è necessario entrare perché le tue liste sono così brevi? Quali misurazioni delle prestazioni ottieni con gli elenchi di elementi 1M? –

+0

Con i tempi che si chiudono, entrano in gioco anche i problemi di cache e GC, ad es. l'inversione della stessa lista di elementi 1k è costosa con un GC generazionale e una cache efficiente, ma gli elenchi di elementi 1M sono probabilmente in grado di sopravvivere all'infermeria o alla regione locale del filo che incorrerà nel sovraccarico e degraderà l'efficienza della cache. –

+0

@JonHarrop, buona chiamata, tempi aggiunti per elementi 1M. – huynhjl

3

Sono in ritardo per questa domanda, ma volevo mostrare come è possibile scrivere un FoldRight coda-ricorsivo senza utilizzare un trampolino pieno; accumulando un elenco di continuazioni (invece di averli chiamano a vicenda quando fatto, che porta ad un overflow stack) e ripiegando loro, alla fine, tipo di come mantenere una pila, ma nel mucchio:

object FoldRight { 

    def apply[A, B](list: Seq[A])(init: B)(f: (A, B) => B): B = { 
    @scala.annotation.tailrec 
    def step(current: Seq[A], conts: List[B => B]): B = current match { 
     case Seq(last) => conts.foldLeft(f(last, init)) { (acc, next) => next(acc) } 
     case Seq(x, xs @ _*) => step(xs, { acc: B => f(x, acc) } +: conts) 
     case Nil => init 
    } 
    step(list, Nil) 
    } 

} 

La piega che avviene alla fine è di per sé ricorsiva. Provalo in ScalaFiddle

In termini di prestazioni, ha prestazioni leggermente peggiori rispetto alla versione di coda.

[info] Benchmark   (length) Mode Cnt Score Error Units 
[info] FoldRight.conts   100 avgt 30 0.003 ± 0.001 ms/op 
[info] FoldRight.conts   10000 avgt 30 0.197 ± 0.004 ms/op 
[info] FoldRight.conts  1000000 avgt 30 77.292 ± 9.327 ms/op 
[info] FoldRight.standard  100 avgt 30 0.002 ± 0.001 ms/op 
[info] FoldRight.standard  10000 avgt 30 0.154 ± 0.036 ms/op 
[info] FoldRight.standard 1000000 avgt 30 18.796 ± 0.551 ms/op 
[info] FoldRight.tailCalls  100 avgt 30 0.002 ± 0.001 ms/op 
[info] FoldRight.tailCalls  10000 avgt 30 0.176 ± 0.004 ms/op 
[info] FoldRight.tailCalls 1000000 avgt 30 33.525 ± 1.041 ms/op 
Problemi correlati