Imported From: https://issues.scala-lang.org/browse/SI-6409?orig=1
Reporter: Robin Palotai (ron)

Robin Palotai (ron) said:
Note also if you are concerned that the above run method holds to the stream head:

scala> @scala.annotation.tailrec def len[A](s: Stream[A], acc: Int = 0): Int = if (s.isEmpty) acc else len(s.tail, acc + 1)
len: [A](s: Stream[A], acc: Int)Int

scala> len(bigElemts)
res3: Int = 999999

scala> len(bigElemts.flatMap(_ => Stream.empty[Int]))
   ... OOM

So it is flatMap holding to the head.

@kmizu said (edited on Sep 25, 2012 2:21:45 AM UTC):
Your example code doesn't indicate that the above run method doesn't holds to the stream head because len method is a tail recursive and the tail recursive method jumps to beginning of the method and rewrite the corresponding parameter s when the method itself is called.

However, my previous comment was also wrong. The reason of this problem is not that the run method holds to the stream head.
The reason of this problems is that flatMap continues to evaluate each thunk of Stream until non-empty sequence is produced.

In len(bigElemts), because s is rewritten to its tail when calling len(s.tail, acc + 1), memory leaks doesn't happen.
In len(bigElemts.flatMap(_ => Stream.empty[Int])), all thunks (LIst.fill(1000)("big")) of bigElemts, the number of bigElemts is 1000000, is evaluated to big List. Then, much memory is consumed. The head of bigElemts cannot be released in the flatMap because bigElemts itself is this reference, which is not rewritable.

Robin Palotai (ron) said:
Kota: Exactly that is my problem. While the flatMap API doc mentions that just like map, flatMap is lazy. One would naively assume (without a deeper understanding of Scala's Stream and its flatMap) that flatMap behaves well memory-wise too.

However when the flatMap's mapper yields a long chain of empty Streams, this behavior does not hold, which is contrary to the (naive and wrong) expectations. An API doc entry would save many hours of debugging (especially in a setup where it is less trivial which Stream transform step is the cause of the leak).

By the way, yielding a long run of empty streams is not artificial (I know you were not stating this, just expressing my opinion), it happened in a live dataset.

@jsuereth said:
scala/scala#1397

Not a fix, but documentation for now. Workaround may be more extensive. Will look into it for 2.10.1.

@adriaanm said:
I seem to remember a related ticket/PR, but couldn't find it.

@Ichoran said:
I don't believe that this problem is actually caused by not having a lazy head. Instead, I think this is exactly what you ask for when you use a Stream: intermediate portions of the stream are kept in memory. Stream actually conflates two different ideas: "I want to be able to iterate from this point over and over again", and "I want to store the results of any computations I do in the future". Stream is the latter (and given the latter it can do the former). Asking to fix this bug is asking to make Stream the former only.

Stream can't know when you call flatMap that you're doing so in a context that allows it to release the head and thus that it shouldn't memoize the results. You've got the same issue with dropWhile or anything else.

So, closing this as wontfix. If someone wants to open a feature request for an immutable collection that is lazy, re-traversable, and non-memoizing (a halfway point between Iterator and Stream), feel free. Otherwise, try to use Iterator in cases like these.

@Ichoran said:
This cannot be fixed due to the type of collection that Stream is. It is not really advisable to document every single method that memoizes to remind the user that Stream memoizes. It's just how Stream works.

@Ichoran said:
Improved docs, hopefully: scala/scala#3805