2012-09-21 13 views
11

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.

+0

Vedere anche il relativo http://stackoverflow.com/questions/12486762/scala-tail-recursive-stream-processor-function-defined-in-trait-holds-reference – ron

+0

ogni possibilità di un pezzo di codice funzionante? Cioè uno che OOMs? – Chris

+0

Chris: certo, confronta i due: https://gist.github.com/3769565 (2.10.0-M7 non migliora per ok.scala) – ron

risposta

2

Il problema, come hai accennato, è che nel codice che hai incollato la funzione filterHelp si mantiene la testa (da qui la soluzione che lo rimuove).

La migliore risposta è semplicemente evitare questo comportamento sorprendente, utilizzare Scalaz EphemeralStream e vederlo non entrambi e molto più veloce in quanto è molto più bello per il gc. Non è sempre così semplice lavorare con, ad es. head è a() => A non A, nessun estrattore ecc., ma è tutto orientato verso un obiettivo, un flusso affidabile di utilizzo.

La funzione filterHelper in genere non ha bisogno di preoccuparsi se si mantiene un riferimento intorno:

import scalaz.EphemeralStream 

@scala.annotation.tailrec 
def filter[A](s: EphemeralStream[A], f: A => Boolean): EphemeralStream[A] = 
    if (s.isEmpty) 
    s 
    else 
    if (f(s.head())) 
     EphemeralStream.cons(s.head(), filterHelp(s.tail() , f)) 
    else 
     filter(s.tail(), f) 

def filterHelp[A](s: EphemeralStream[A], f: A => Boolean) = 
    filter(s, f) 

def s1 = EphemeralStream.range(1, big) 

mi piacerebbe andare al punto di dire che se non si ha un motivo valido per utilizzare Stream (altro dipendenze di librerie ecc.) quindi rimani fedele a EphemeralStream, ci sono molte meno sorprese lì.

+0

ES è un buon punto. Avevo bisogno di Stream perché la sorgente sottostante non è un calcolo ma un iteratore mutabile. So che starei meglio usando Iteratees (o simili, vedi http://stackoverflow.com/questions/12496654/is-there-an-iteratee-like-concept-which-pulls-data-from-multiple- fonti). – ron

3

Una soluzione possibile consiste nel rendere il metodo recHelp non contenere il riferimento alla testa del flusso. Ciò può essere ottenuto facendo passare una corrente avvolto ad esso, e mutando l'involucro di cancellare il riferimento da esso:

@tailrec 
final def rec[A](as: Stream[A]): Stream[B] = 
    if (a.isEmpty) Stream.empty    
    else if (someCond) rec(a.tail)   
    else { 
    // don't inline and don't define as def, 
    // or anonymous lazy wrapper object would hold reference 
    val tailRef = new AtomicReference(a.tail) 
    someB(a.head) #:: recHelp(tailRef) 
    } 

@tailrec 
final def recHelp[A](asRef: AtomicReference[Stream[A]]): Stream[B] = 
    // Note: don't put the content of the holder into a local variable 
    rec(asRef.getAndSet(null)) 

Il AtomicReference è solo convenienza, atomicity non è necessario in questo caso, qualsiasi oggetto titolare semplice farebbe .

Si noti inoltre che dal recHelp viene inserito uno stream Cons coda, pertanto verrà valutato solo una volta e anche Cons si occuperà della sincronizzazione.

Problemi correlati