具有 Stream 类型的 Scala 递归实现

Question

我已经开始在 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
}

但是，如果我们在 sqrtGuess 之外定义 isSufficient 并将其应用于 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 的第一个实现发生了什么？我正在尝试使用替代模型来证明它但它似乎没有任何问题。

Answer 1

我假设您使用的是 Scala 2.12，因为 Stream 在 Scala 2.13 中已弃用，弃用消息如下：

Use LazyList (which is fully lazy) instead of Stream (which has a lazy tail only)

我没有真正的证据证明我要说的话，但我可以假设这是正在发生的事情：

在非工作示例中，您尝试根据 x = 4.2 和 guess = 1.0 生成列表。计算出的下一个元素被过滤器丢弃。所以下一个不会添加到流中。因此 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)
}

具有 Stream 类型的 Scala 递归实现

Scala recursive implementation with Stream type

recursion

scala

scala-streams