StackOverFlowError When Applying Filter to a Stream

[co.kl...@gmail.com]

Hello,

Please can some one explain why the following code blows the stack:

val fibs: Stream[BigInt] = BigInt(0) #:: BigInt(1) #:: fibs.zip(fibs.tail).map { n => n._1 + n._2 }.takeWhile(x => x < 4000000).filter(x => x % 2 == 0)

scala> fibs foreach println
0
1
java.lang.StackOverflowError

If I take out the filter and apply it to the stream in another expression as follows, it is fine:

scala> val fibs: Stream[BigInt] = BigInt(0) #:: BigInt(1) #:: fibs.zip(fibs.tail).map { n => n._1 + n._2 }.takeWhile(x => x < 4000000)
fibs: Stream[scala.math.BigInt] = Stream(0, ?)

scala> fibs filter ( x => x % 2 == 0)
res8: scala.collection.immutable.Stream[scala.math.BigInt] = Stream(0, ?)

scala> fibs filter ( x => x % 2 == 0) foreach println
0
2
8
34
144
610
2584
10946
46368
196418
832040
3524578

Why does it blow the stack with the first approach but not the second?

Thanks

Iftikhar

[Simon Schäfer]

The first time, the filter is part of fibs, the second time it is part of another stream accessing fibs. In the first case there are simply not enough values left to continue the stream.

--
You received this message because you are subscribed to the Google Groups "scala-language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-languag...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[co.kl...@gmail.com]

Could you expand on this bit please:

In the first case there are simply not enough values left to continue the stream.

[Simon Schäfer]

On 06.08.2015 02:27, co.kl...@gmail.com wrote:

Could you expand on this bit please:

In the first case there are simply not enough values left to continue the stream.

Well, your Stream contains two values: 0 and 1. They are both accessed and when the third value needs to be accessed it needs to be computed. The third value is 0+1==1. Given that it is odd, it is skipped by the filter. For the fourth value the third one needs to exist, which is not the case. Therefore it also can't be computed.

In the second example, the second 1 is not skipped. Instead it is stored in the original Stream. The filter only skips values by constructing the second Stream but the original Stream is never touched and therefore all odd values can skipped without further problems.

[Andrew Phillips]

Hi Iftikhar

> For the fourth value the third one needs to exist, which is not the case. Therefore it also can't be computed.

Here's another, reduced example that demonstrates this (2.11.6 REPL):

val naturals: Stream[Int] = 1 #:: (naturals map { _ + 1 })

scala> naturals filter { _ != 3 } take 3 foreach println

1

2

4

val filtered: Stream[Int] = 1 #:: (filtered map { _ + 1 } filter { _ != 3 })

filtered take 2 foreach println

scala> filtered take 2 foreach println

1

2

scala> filtered take 3 foreach println

1

2

java.lang.StackOverflowError

  ...

  

The stream naturals can always produce a next value, because we have a starting value and the next value is simply the previous value, plus 1. So in order to take three values from the stream naturals filter { _ != 3 }, we can simply keep taking values from naturals until three make it past the filter.

The stream filtered, however, gets "stuck" producing its third value. The first value is easy - it's already defined as 1. For the second value, we need the first element from the stream filtered map { _ + 1 } filter { _ != 3 }. We start with the first element from filtered, add 1 to it and see if it makes it past the filter. It does, so the second element of filtered = the first element of filtered map { _ + 1 } filter { _ != 3 } = 2.

For the third value of filtered, we need the second value of filtered map { _ + 1 } filter { _ != 3 }. We take the second (just calculated) value of filtered and add 1, but the result doesn't make it past the filter. So we try to take the next - third - value of filtered...but that is the value we are just trying to calculate. Endless loop.

In short, filtered blows up because an element ends up being defined in terms of itself. With naturals, all elements are defined in terms of previous - already calculated - values only.

Regards

ap

[Oliver Ruebenacker]

     Hello,

  Why does an endless loop lead to stack overflow?

     Best, Oliver

Oliver Ruebenacker

Senior Software Engineer, Diabetes Portal, Broad Institute

[Simon Schäfer]

On 07.08.2015 11:32, Oliver Ruebenacker wrote:
>
> Hello,
>
> Why does an endless loop lead to stack overflow?

Given the recursive definition of the Stream, the endless loop is also
recursive and therefore blows up former or later.

[co.kl...@gmail.com]

Simon, Andrew,

Thanks for the breakdown; makes sense now.