Getting Lazy With Scala

In this blog, we will talk about lazy evaluation in Scala. But first, a question: How can we add efficiency to our application?

Efficiency is achieved not just by running things faster, but by avoiding things that shouldn’t be done in the first place.

In functional programming, lazy evaluation means efficiency. Laziness lets us separate the description of an expression from the evaluation of that expression. This gives us a powerful ability — we may choose to describe a “larger” expression than we need, and then evaluate only a portion of it. There are many ways to achieve lazy evaluation in Scala, i.e using the lazy keyword, views, streams, etc.

For example:

scala> val num = 3
num: Int = 3

scala> lazy val lazyNum = 3
lazyNum: Int =

scala> lazyNum
res0: Int = 3

Here, if you notice, when I defined the val named num, it has a value of 3. But when I defined another val named lazyNum with a lazy keyword, it has no value because it will be computed lazily. The difference between them is that a val is executed when it is defined, whereas a lazy val is executed when it is accessed the first time. So when we used lazyNum, it has a value of 3 now.

In contrast to a method (defined with def), a lazy val is executed once and then never again. This can be useful when an operation takes a long time to complete and when it is not sure if it is later used.

Scala supports two types of collections:

1. Strict Collections, i.e. List, Map, Set, etc

2. Non-Strict Collections, i.e. Streams

Strict collection means that they all are eagerly evaluated, i.e List, Set, Vector, Map, etc.

For example, if we create a list of 10 elements, memory is allocated for all those elements immediately.

scala> val list = (1 to 10).toList
list: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

Here, the head of lazyList is eagerly computed, but the tail has not been computed yet.

Streams

A stream is a collection like a list except that it is lazily evaluated. That’s why we can have infinite elements in a stream. In streams, elements are being computed on demand. We create a list using the cons :: operator. Similarly, we build streams using the #:: operator.

For example:

scala> val stream = 1 #:: 2 #:: 3 #:: Stream.empty
stream: scala.collection.immutable.Stream[Int] = Stream(1, ?)

We have created a Stream having three elements: 1, 2, and 3.

Our Stream is eagerly evaluated at the head. Therefore, the head of the stream has been printed, but the tail is lazily computed. That’s why it has not been computing yet. It will be computed on demand. The toStream method can convert any collection to a Stream.

For example, find the first 10 primes after 100.

scala> def isPrime(number: Int) =
| number > 1 && !(2 to number - 1).exists(e => e % number == 0)
isPrime: (number: Int)Boolean

scala> def generatePrimes(starting: Int): Stream[Int] = {
| if(isPrime(starting))
| starting #:: generatePrimes(starting + 1)
| else
| generatePrimes(starting + 1)
| }
generatePrimes: (starting: Int)Stream[Int]

scala> generatePrimes(100).take(10)
res8: scala.collection.immutable.Stream[Int] = Stream(100, ?)

generatePrimes has an infinite number of primes, and we are interested in getting only 10 primes greater than 100. When we apply the take method, it still does not give us the result — because Streams do not evaluate until they are no longer needed.

How to Get the Value From a Stream?

We could either use a force method to get the value from a Stream, or we could use the toList method to get a list of primes.

scala> generatePrimes(100).take(10).force
res9: scala.collection.immutable.Stream[Int] = Stream(100, 101, 102, 103, 104, 105, 106, 107, 108, 109)

scala> generatePrimes(100).take(10).toList
res10: List[Int] = List(100, 101, 102, 103, 104, 105, 106, 107, 108, 109)

View

A view is a special kind of collection that represents some base collection but implements all methods lazily.

For example:

scala> (1 to 1000000000).filter(_ % 2 != 0).take(20).toList
java.lang.OutOfMemoryError: GC overhead limit exceeded

Here, I have tried to create a list of a million elements and taking first 20 odd numbers. OOPS! I got OOM error.  But with the view:

scala> (1 to 1000000000).view.filter(_ % 2 != 0).take(20).toList
res2: List[Int] = List(1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39)

This time, there is no OOM error. Tthe reason is that the Stream did not allocate memory for all million elements. Memory is allocated only for needed elements.

The difference between a Stream and a view is that views are lazy in evaluating methods whereas Streams are ultimately lazy. A stream has no value. It generates values only when we ask for them.  Besides that, Streams cache the results, but views don't. In a view, elements are recomputed each time they are accessed. In a stream, elements are retained as they are evaluated.

Let me summarize what we have talked about so far. Non-strictness is a fundamental technique for implementing efficient and modular functional programs. Streams and views are ways to achieve lazy evaluation in Scala. They help to avoid creating intermediate collections and make code faster.

Please feel free to give suggestions and comment!

References

1. View
2. Stream
3. Functional Programming in Scala