A good example to show the differences between strict and lazy evaluation in Scala

Way back in April, 2014, I was having my cancerous thyroid removed, and Erik Meijer wrote an ACM article titled, The Curse of the Excluded Middle, “Mostly functional” programming does not work. I just got around to reading his article today, where he makes some points about why a hybrid FP/OOP approach doesn’t work.

I don’t want to comment on his article — other than to say that it’s an interesting read — but what I am interested in his first example, which was written in C# by Gavin Bierman. It’s an interesting example that does a great job of demonstrating the difference between “strict” and “lazy” evaluation, so I converted his example to Scala, and I’m sharing that code below.

The example, using a “lazy” approach

The easiest way to show the problem is to show the code for it, so I’ll get right to it:

object Test1WithFilterLazy extends App {

    def lessThan30(i: Int): Boolean = {
        println(s"\n$i less than 30?")
        i < 30
    } 

    def moreThan20(i: Int): Boolean = {
        println(s"$i more than 20?")
        i > 20
    } 

    val a = List(1, 25, 40, 5, 23)
    val q0 = a.withFilter(lessThan30)
    val q1 = q0.withFilter(moreThan20)
    for (r <- q1) println(s"$r")

}

The question is, “What do you think this code will print?

Before you answer that, if you don’t know what the withFilter method does, here’s an abbreviated description from its Scaladoc:

Creates a non-strict filter of this traversable collection. Note: the difference between `c filter p` and `c withFilter p` is that the former creates a new collection, whereas the latter only restricts the domain of subsequent map, flatMap, foreach, and withFilter operations.

Note that non-strict is also called “lazy,” or “deferred execution,” as Mr. Meijer refers to it.

Given that information, here’s what that code prints:

1 less than 30?
1 more than 20?

25 less than 30?
25 more than 20?
25

40 less than 30?

5 less than 30?
5 more than 20?

23 less than 30?
23 more than 20?
23

How that code works

Does it surprise you that the two functions are called only when each number in the list is reached? That is, is it a surprise that the output shows that the algorithm runs like this:

  1. The first number in the list is 1. Is 1 less than 30? Yes. Okay, is 1 greater than 20? No. Okay, move on.
  2. The second number in the list is 25. Is 25 less than 30? Yes. Okay, is 25 greater than 20? Yes. Sweet, we found a number that matches both conditions, add it to our result.

This algorithm continues for the remaining elements in the list.

If you’re not familiar with lazy evaluation, the surprise here is that the original list isn’t immediately reduced to a smaller list of elements whose value is less than 30 in this line of code:

val q0 = a.withFilter(lessThan30)

In a “strict” world, q0 would look like this after that line of code:

List(1, 25, 5, 23)  //notice that '40' was removed

But when using withFilter as shown, this code isn’t even called until it’s “demanded” by this for expression:

for (r <- q1) println(s"$r")

You can prove that for yourself by removing this for expression and then running this example, at which time you’ll see no output.

The same example, using a “strict” approach

You can see the differences between the lazy and strict worlds by changing that code to use the filter method, which is strict, instead of withFilter (and changing the println statements a little):

object Test2FilterStrict extends App {

    def lessThan30(i: Int): Boolean = {
        println(s"$i less than 30?")
        i < 30
    } 

    def moreThan20(i: Int): Boolean = {
        println(s"$i more than 20?")
        i > 20
    } 

    val a = List(1, 25, 40, 5, 23)
    val q0 = a.filter(lessThan30);  println("")
    val q1 = q0.filter(moreThan20); println("")
    for (r <- q1) println(s"$r")

}

If you like the strict evaluation world, this output can be a little more comforting:

1 less than 30?
25 less than 30?
40 less than 30?
5 less than 30?
23 less than 30?

1 more than 20?
25 more than 20?
5 more than 20?
23 more than 20?

25
23

As you can see from that output, all of the values are first run through the lessThan30 function, and then the remaining values after that are run through the moreThan20 function. You can tell this (a) from the order of the printed output, and (b) because the value 40 is not passed to the moreThan20 function.

The difference in output

The difference in the output is really striking. Here are both outputs, shown side by side:

Lazy Output Strict Output
1 less than 30?
1 more than 20?

25 less than 30?
25 more than 20?
25

40 less than 30?

5 less than 30?
5 more than 20?

23 less than 30?
23 more than 20?
23
1 less than 30?
25 less than 30?
40 less than 30?
5 less than 30?
23 less than 30?

1 more than 20?
25 more than 20?
5 more than 20?
23 more than 20?

25
23

That output shows the differences between the two different worlds, and with the exception of changing the println statements, all I did was switch withFilter to filter.

Summary

I don’t have a major conclusion here at the moment, but if you’re not used to the differences between strict and lazy evaluation, I thought this was a nice example, i.e., a nice way to show the differences between the two approaches.

See Also