CODEWITHSUNDEEP
scala
Jatin
Jatin

Reputation: 31724

Understanding Streams

There is one pattern that reappears again and again and I haven't been able to understand it completely, for example the below code to calculate isPrime

class S99Int(val start: Int) {
  import S99Int._
  def isPrime: Boolean =
    (start > 1) && (primes takeWhile ( _ <= Math.sqrt(start) ) forall ( start % _ != 0 ))
}

object S99Int {
  implicit def int2S99Int(i: Int): S99Int = new S99Int(i)
  val primes = Stream.cons(2, Stream.from(3, 2) filter { _.isPrime })
}
import S99Int._

24 isPrime        //returns false

What I dont understand is that: primes in the filter uses isPrime. But again the def isPrime uses the same primes to take elements. Isn't it like an infinite loop where one thing asks another and then that thing again to one-self. Though the code works perfect.

Upvotes: 2

Views: 412

Answers (1)

gzm0
gzm0

Reputation: 14842

Streams in Scala are lazily evaluated. That means only the values up to the last value you actually need are calculated. What does this mean for your prime example:

isPrime does not use the whole primes stream, but only a portion of it:

(primes takeWhile ( _ <= Math.sqrt(start) )

It uses only the portion of it which is smaller than the square root of the number you want to test (and the next one, as you have to evaluate it to see it is too big). When now primes calls isPrime again for one of those smaller numbers, the required part of primes is even smaller. This goes on until you reach the initial 2.

Think of it as a mutually recursive functions:

  • isPrime as is
  • primes could be considered as primesUpTo(n: Int)

And then:

class S99Int(val start: Int) {
  import S99Int._
  def isPrime: Boolean =
    (start > 1) && (S99Int.primesUpTo(math.sqrt(start).toInt) forall ( start % _ != 0 ))
}

object S99Int {
  implicit def int2S99Int(i: Int): S99Int = new S99Int(i)
  def primesUpTo(n: Int): IndexedSeq[Int] = {
    if (n >= 2) 2 +: (3 to n) filter { _.isPrime }
    else IndexedSeq.empty
  }
}

The only thing the Stream achieves for you is to cache values from primesUpTo(n: Int) so that they are calculated only once and to make the expression UpTo more intuitive for a functional programmer.

Upvotes: 6

Related Questions