Scala的Stream和StackOverflowError

Question

考虑这段代码(取自Martin Odersky的" 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

它工作得很好.请注意,sieve事实上它不是尾递归(或者是它？),即使Stream尾部是懒惰的.

但是这段代码:

def sieve(n: Int): Stream[Int] = {
  n #:: sieve(n + 1).filter(_ % n != 0)
}

val primes = sieve(2)
primes.take(1000).toList

抛出StackOverflowError.

第二个例子有什么问题？我filter想搞砸了,但我不明白为什么.它返回一个Stream,所以它不会让评价急切(我是对的吗？)

Answer 1

您可以使用一些跟踪代码突出显示该问题:

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

我们可以运行它并检查计数器:

scala> counter1
res2: Int = 100

scala> counter2
res3: Int = 540

所以在第一种情况下,调用堆栈的深度是质数的数量,而在第二种情况下,它是最大的素数本身(嗯,减去1).