Quando si scrive una funzione che funziona su Stream
(s), esistono diverse nozioni di ricorsione. Il primo senso semplice non è ricorsiva sul piano del compilatore, dal momento che la coda se non valutati istantaneamente così la funzione restituisce immediatamente, ma il flusso restituito è ricorsiva:Come scrivere una funzione ricorsiva in coda senza perdite utilizzando Stream.cons in Scala?
final def simpleRec[A](as: Stream[A]): Stream[B] =
if (a.isEmpty) Stream.empty
else someB(a.head) #:: simpleRec(a.tail)
È possibile che questo concetto di ricorsione non causa alcun problema . La seconda è veramente ricorsiva in coda al livello compilatore:
@tailrec
final def rec[A](as: Stream[A]): Stream[B] =
if (a.isEmpty) Stream.empty // A) degenerated
else if (someCond) rec(a.tail) // B) tail recursion
else someB(a.head) #:: rec(a.tail) // C) degenerated
Il problema è che il caso C)
viene rilevato dal compilatore come una chiamata non tailrec, anche se non v'è alcuna chiamata effettiva condotta. Ciò può essere evitato depurando la coda flusso in una funzione di supporto:
@tailrec
final def rec[A](as: Stream[A]): Stream[B] =
if (a.isEmpty) Stream.empty
else if (someCond) rec(a.tail) // B)
else someB(a.head) #:: recHelp(a.tail)
@tailrec
final def recHelp[A](as: Stream[A]): Stream[B] =
rec(as)
Mentre compila, questo approccio si traduce poi in una perdita di memoria. Dal momento che la coda ricorsiva rec
viene infine chiamata dalla funzione recHelp
, il frame di stack della funzione recHelp
contiene un riferimento alla testa di vapore e non consente al flusso di essere trituratamente raccolto finché non viene restituita la chiamata rec
, che può essere piuttosto lunga (in termini di passaggi di ricorsione) in base al numero di chiamate a B)
.
Si noti che anche nel caso helperless, se il compilatore ha consentito a @tailrec, la perdita di memoria potrebbe essere ancora presente poiché la coda del flusso lento creerebbe in effetti un oggetto anonimo contenente un riferimento alla testa del flusso.
Vedere anche il relativo http://stackoverflow.com/questions/12486762/scala-tail-recursive-stream-processor-function-defined-in-trait-holds-reference – ron
ogni possibilità di un pezzo di codice funzionante? Cioè uno che OOMs? – Chris
Chris: certo, confronta i due: https://gist.github.com/3769565 (2.10.0-M7 non migliora per ok.scala) – ron