Scala Stream and StackOverflowError

Question

Consider this code (taken from Martin Odersky's Principles of Functional Programming in Scala ):

def sieve(s: Stream[Int]): Stream[Int] = { s.head #:: sieve(s.tail.filter(_ % s.head != 0)) } val primes = sieve(Stream.from(2)) primes.take(1000).toList 

It works great. Note that sieve is NOT really a tail recursive (or is it?), Although the Stream tail is lazy.

But this code:

 def sieve(n: Int): Stream[Int] = { n #:: sieve(n + 1).filter(_ % n != 0) } val primes = sieve(2) primes.take(1000).toList 

throws StackOverflowError .

What is the problem with the second example? I think filter parses things, but I can't figure out why. It returns a Stream , so it cannot make an evaluation look (am I right?)

Answer 1

You can highlight the problem with the tracking code:

 var counter1, counter2 = 0 def sieve1(s: Stream[Int]): Stream[Int] = { counter1 += 1 s.head #:: sieve1(s.tail.filter(_ % s.head != 0)) } def sieve2(n: Int): Stream[Int] = { counter2 += 1 n #:: sieve2(n + 1).filter(_ % n != 0) } sieve1(Stream.from(2)).take(100).toList sieve2(2).take(100).toList 

We can run this and check the counters:

 scala> counter1 res2: Int = 100 scala> counter2 res3: Int = 540 

Thus, in the first case, the depth of the call stack is the number of primes, and in the second, the largest prime (well, minus one).

Answer 2

None of them are tail recursive.

Using the tailrec annotation, you will find out if the function is tail recursive.

Adding @tailrec to the two functions above gives:

 import scala.annotation.tailrec @tailrec def sieve(s: Stream[Int]): Stream[Int] = { s.head #:: sieve(s.tail.filter(_ % s.head != 0)) } @tailrec def sieve(n: Int): Stream[Int] = { n #:: sieve(n + 1).filter(_ % n != 0) } 

The download shows that both definitions are not recursive:

 <console>:10: error: could not optimize @tailrec annotated method sieve: it contains a recursive call not in tail position s.head #:: sieve(s.tail.filter(_ % s.head != 0)) ^ <console>:10: error: could not optimize @tailrec annotated method sieve: it contains a recursive call not in tail position n #:: sieve(n + 1).filter(_ % n != 0)