Getting Lazy With Scala

Table of contents

Reading Time: 4 minutes

In this blog, we will talk about lazy evaluation in Scala. How we can 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 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 val naming num, it has value 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 again lazyNum, it has value 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 Collection 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)

But, non-strict collections like streams, are by default lazy evaluated. They are evaluated on demand. For example, if I create a stream of 10 numbers it won’t create it.

scala> val lazyList = (1 to 10).toStream
lazyList: scala.collection.immutable.Stream[Int] = Stream(1, ?)

Here, head of lazyList is eagerly computed but the tail has not 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 cons :: operator, similarly, we build stream using #:: 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.

Since Stream is eagerly evaluated at the head. Therefore, 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 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 10 primes only greater than 100. When we apply the take method, it still does not give us the result. Because Streams does not evaluate until it is no longer needed.

How to get the value from a stream?

We could either use force method to get the value from 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 million elements and taking first 20 odd numbers. OOPS! I got OOM error. But with 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, the reason is stream has never allocated memory for all million elements. Memory is allocated only for needed elements.

The difference between Stream and view is lazy view is lazy in evaluating the methods whereas Stream is ultimately lazy. A stream has no value. It generates value only when we ask for it. So, it is possible values are already there in case of view. Besides that, Streams caches the result but the view doesn’t. In a view, elements are recomputed each time they are accessed. In a stream, elements are retained as they are evaluated.

Let me summarise what we have talked so far, we talked about non-strictness as a fundamental technique for implementing efficient and modular functional programs. Stream and views are ways to achieve lazy evaluation in scala. It helps to avoid creating intermediate collections and makes code faster.

Please free to give suggestions and comment!

References: