带有Stream类型的Scala递归实现
我已经开始在 Coursera 上学习 Scala 并且有一些关于squareRootGuess实现的问题如下
我正在尝试实施标准来过滤sqrtGuess定义中的准确猜测，如下所示，但它给了我堆栈溢出错误。
def sqrtGuess(x: Double): Stream[Double] = {
def nextGuess(guess: Double): Double = (guess + x / guess)/2
def isSufficient(guess: Double): Boolean = math.abs(x - guess*guess)/x < 0.001
def guesses: Stream[Double] =
1 #:: guesses.map(nextGuess).filter(isSufficient)
guesses
}
但是，如果我们在外部定义 isSufficientsqrtGuess并应用于sqrtGuess流，效果会很好。
def sqrtGuess(x: Double): Stream[Double] = {
def nextGuess(guess: Double): Double = (guess + x / guess)/2
def guesses: Stream[Double] =
1 #:: guesses.map(nextGuess)
guesses
}
def isSufficient(guess: Double, x: Double): Boolean = math.abs(x - guess*guess)/x < 0.001
sqrtGuess(4.2).filter(isSufficient(_, 4.2)).take(10).toList
我想知道在第一次实现中会发生什么sqrtGuess？我正在尝试使用替换模型来证明它，但它似乎没有任何问题。
回答
我将假设您使用的是 Scala 2.12，因为Stream在 Scala 2.13 中已弃用，并带有以下弃用消息：
使用 LazyList（完全惰性）而不是 Stream（只有惰性尾部）
我没有真正的证据来证明我要说的话，但我可以假设这是正在发生的事情：
在非工作示例中，您尝试基于x = 4.2、 和生成列表guess = 1.0。计算出的下一个元素被过滤器丢弃。所以 next 不会添加到流中。因此，guesses总是无法为流创建新元素，而且我们永远不会在流中获得 10 个元素。堆栈溢出是由于无限递归引起的。
为了过滤，您需要首先创建流，并对其进行过滤：
def sqrtGuess1(x: Double): Stream[Double] = {
def nextGuess(guess: Double): Double = (guess + x / guess)/2
def isSufficient(guess: Double): Boolean = math.abs(x - guess*guess)/x < 0.001
def guesses: Stream[Double] =
1 #:: guesses.map(nextGuess)
guesses.filter(isSufficient)
}