lazy evaluation and the Sieve of Eratosthenes in Scala

         Lazy evaluation can be described as an expression that has a value, but that is not evaluated until it's actually needed. Some functional languages are described as Pure Lazy  to reflect the fact that all evaluation is performed on demand. Haskell is on such language. Scala has both aspects of strict evaluation and lazy evaluation, as such it couldn't be referred to as 'pure' in either sense.

          By means of the simplest example to illustrate Lazy evaluation, consider the following interaction with the Scala :

scala> lazy val a = b + 1; lazy val b = 1;
a: Int = <lazy>
b: Int = <lazy>
scala> a
res9: Int = 2
scala> b
res10: Int = 1

        This illustrates lazy evaluation, without defining the 'vals' as lazy the statement lazy val a = b + 1; lazy val b = 1; as val a = b + 1; val b = 1; couldn't be evaluated because b would be undefined when evaluating a!.

        The examples are based on the Sieve of Eratosthenes. Eratosthenes was an ancient Greek Mathematician from 276 BC – c. 195 BC. The Sieve of Eratosthenes is a ancient algorithm for finding prime numbers from 2 .. n. Stated simply, this algorithm can be expressed as :

• Create a list of all the numbers from 2 .. n.
• Starting at p = 2
• Strike out all multiples of p up until n from the list
• Let p now be the first (lowest) number that has not been struck-off the list
• Repeat the last two steps until p^2 > n
• All remaining numbers not struck from the list are prime

        The following Scala code shows  the way to implement the Sieve using Scala Lazy streams.

 

object Primes1 {
    def primes : Stream[Int] = {
        var is = Stream from 2
        def sieve(numbers: Stream[Int]): Stream[Int] = {
           Stream.cons(
           numbers.head,
           sieve(for (x <- numbers.tail if x % numbers.head > 0) yield x))
 }
 sieve(is)
}
def main(args : Array[String]) = {
    primes take 100 foreach println
}
}
object Primes2 {
    def primes = {
       def sieve(is: Stream[Int]): Stream[Int] = {
           val h = is.head
           Stream.cons(h, sieve(is filter (_ % h > 0)))
 }
 sieve(Stream.from(2))
}
def main(args: Array[String]) {
    println(primes take 100 toList)
}
}