Scala recursive implementation with Stream type

Question

I have started studying Scala on Coursera and have some question on squareRootGuess implementation as follow

I am trying to implement criteria to filter the accurate guess inside the sqrtGuess definition as shown below, but it gives me stack overflow error.

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
}

But if we define isSufficient outside the sqrtGuess and apply to sqrtGuess stream it works out well.

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

I wonder what is happen in the first implementation of sqrtGuess? I am trying to use substitution model to prove it but it doesn't seems to have any problem.

Answer 1

I'm going to assume you are using Scala 2.12 since Stream is deprecated in Scala 2.13, with the following deprecation message:

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

I have no true evidence to what I'm about to say, but I can assume that this what is going on:

In the non-working example, you are trying to generate a list, based on x = 4.2, and guess = 1.0. The next element that is calculated is dropped by the filter. So the next is not added to the stream. Therefore the guesses is constantly failing to create a new element to the stream, and we never get to 10 elements in the stream. The stack overflow is caused due to the endless recursion.

In order to filter, you need to first create the stream, and filter on it:

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)
}