Scala tail-recursive Stream processor function def

问题:

In the following situation

trait T {

 @tailrec
 def consume[A](as: Stream[A]): Unit = {
    if (as.isEmpty) ()
    else consume(as.tail)
  }
 }

object O extends T

calling O.consume(Range(1, N).toStream) with N big enough, the program will run out of memory, or at least will consume O(N) instead of the needed O(1).

回答1:

The tail-recursive method is generated for the trait. The method entry in the extender of the trait (here O) forwards the call to the method of the trait, but while doing so, it keeps a reference to the head of the Stream.

Thus the method is tail-recursive, but memory still can't be released. Remedy: Don't define Stream functions in traits, just directly in objects.

An alternative is scalaz's EphemeralStream, which holds weak references to the stream head and tail, and recomputes them on demand.

回答2:

There is a simple workaround. Just wrap your tail recursive stream consumer in another function that receives the stream via a by-name parameter:

import scala.annotation.tailrec

trait T {
  def consume[A](as: => Stream[A]): Unit = {
    @tailrec
    def loop[A](as: Stream[A]): Unit = {
        if (as.isEmpty) ()
       else loop(as.tail)
    }
    loop(as)
  }
}

object O extends T {
  def main(args: Array[String]): Unit = 
    O.consume(Range(1, 1000000000).toStream) 
}

The forwarder method will hold a reference to a function computing an expression the result of which is a stream:

public final class O$ implements T {
  public static final MODULE$;
  // This is the forwarder:
  public <A> void consume(Function0<Stream<A>> as) {
    T.class.consume(this, as);
  }
     .  .  .      

  public void main(String[] args) {
    consume(new AbstractFunction0() {
      public final Stream<Object> apply() {
        return package..MODULE$.Range().apply(1, 1000000000).toStream();
      }
    });
  }
}