Re: StackOverFlowError When Applying Filter to a Stream

     Hello,

  Why does an endless loop lead to stack overflow?

     Best, Oliver

On Fri, Aug 7, 2015 at 12:15 AM, Andrew Phillips <[email protected]>
wrote:

> 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] 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].
>> 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.
>



-- 
Oliver Ruebenacker
Senior Software Engineer, Diabetes Portal
<http://www.type2diabetesgenetics.org/>, Broad Institute
<http://www.broadinstitute.org/>

-- 
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.