Re: StackOverFlowError When Applying Filter to a Stream

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

On Thursday, August 6, 2015 at 6:24:00 PM UTC-4, Simon Schäfer wrote:
>
>
>
> On 06.08.2015 02:27, [email protected] <javascript:> 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.
>
>
> On Wednesday, 5 August 2015 19:46:47 UTC+1, Simon Schäfer wrote: 
>>
>> 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.
>>
>> On 05.08.2015 20:16, [email protected] wrote:
>>
>> 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 println01
>> 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 println02834144610258410946463681964188320403524578
>>
>> Why does it blow the stack with the first approach but not the second?
>>
>>
>> Thanks
>>
>> Iftikhar
>> -- 
>> 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 [email protected].
>> For more options, visit https://groups.google.com/d/optout.
>>
>>
>> -- 
> 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 [email protected] <javascript:>.
> For more options, visit https://groups.google.com/d/optout.
>
>
>

-- 
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 [email protected].
For more options, visit https://groups.google.com/d/optout.