考虑以下代码(取自 Martin Odersky 的“Functional programming principles in Scala”类(class)):
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
,所以它不会让评估急切(我说得对吗?)
最佳答案
您可以使用一些跟踪代码突出显示问题:
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
因此,在第一种情况下,调用堆栈的深度是质数的数量,而在第二种情况下,它是最大的质数本身(好吧,减一)。
关于Scala 的 Stream 和 StackOverflowError,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13333775/