¿Cómo escribir la función recursiva de cola sin fugas usando Stream.cons en Scala?

Question

Al escribir una función que funciona en Stream (s), existen diferentes conceptos de recursión. El primer sentido simple no es recursivo en el nivel del compilador, ya que la cola si no se evalúa al instante por lo que la función devuelve de inmediato, pero el flujo devuelto es recursivo:

final def simpleRec[A](as: Stream[A]): Stream[B] = 
    if (a.isEmpty) Stream.empty    
    else someB(a.head) #:: simpleRec(a.tail) 

la idea anterior de la recursividad no causa ningún problema . El segundo es verdaderamente recursiva de cola en el nivel del compilador:

@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 

El problema aquí es que el caso C) es detectado por el compilador como una llamada no tailrec, incluso si no hay una llamada real llevado a cabo. Esto se puede evitar mediante la factorización la cola de corriente en una función auxiliar:

@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) 

Mientras que compila, este enfoque eventualmente resulta en una pérdida de memoria. Dado que finalmente se llama al rec recursivo de cola desde la función recHelp, el marco de pila de la función recHelp contiene una referencia al cabezal de vapor y no permite que el flujo sea recogido hasta que devuelve la llamada rec, que puede ser bastante larga. (en términos de pasos de recursión) según el número de llamadas al B).

Tenga en cuenta que incluso en el caso helperless, si el compilador permitía el @tailrec, la pérdida de memoria puede estar presente ya que la cola de flujo diferida crearía en efecto un objeto anónimo con referencia al encabezado de flujo.

Answer 1

El problema, como has insinuado, es que en el código pegaste la función filterHelp mantiene la cabeza (de ahí que tu solución lo elimine).

La mejor respuesta es simplemente evitar este comportamiento sorprendente, use Scalaz EphemeralStream y vea que no se mueva mucho más rápido ya que es mucho mejor que el gc. No siempre es tan fácil trabajar con, por ejemplo, la cabeza es a() => A no A, no hay extractores, etc., pero todo está orientado a un uso de corriente objetivo y confiable.

Su función filterHelper generalmente no tiene que preocuparse por si se mantiene una referencia en torno a:

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) 

me gustaría ir tan lejos como para decir que a menos que tenga una razón de peso para utilizar la corriente (otra dependencias de la biblioteca, etc.) y luego simplemente se adhieren a EphemeralStream, allí hay menos sorpresas.

Answer 2

Una posible solución es hacer que el método recHelp no mantenga la referencia al encabezado de la secuencia. Esto puede lograrse haciendo pasar una corriente envuelta a ella, y la mutación de la envoltura para borrar la referencia de ella:

@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)) 

El AtomicReference se acaba de conveniencia, la atomicidad no es requerida en este caso, cualquier objeto titular sencilla haría .

También tenga en cuenta que ya que recHelp está envuelto en una cola Cons cola, por lo tanto, solo se evaluará una vez, y Cons también se ocupa de la sincronización.