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