5 Strictness and laziness

In chapter 3, we talked about purely functional data structures, using singly linked lists as an example. We covered a number of bulk operations on lists: map, filter, foldLeft, foldRight, zipWith, and so on. We noted that each of these operations makes its own pass over the input and constructs a fresh list for the output.

Imagine you had a deck of cards and were asked to remove the odd-numbered cards and then flip over all the queens. Ideally, you’d make a single pass through the deck, looking for queens and odd-numbered cards at the same time. This is more efficient than removing the odd cards and then looking for queens in the remainder─and yet the latter is what Scala is doing. Consider the following code:¹

In this expression, map(_ + 10) will produce an intermediate list that then gets passed to filter(_ % 2 == 0), which in turn constructs a list that gets passed to map(_ * 3), which then produces the final list. In other words, each transformation will produce a temporary list that only ever gets used as input to the next transformation and is then immediately discarded.

Think about how this program will be evaluated. If we manually produce a trace of its evaluation, the steps would look something like this.

5.1 Strict and nonstrict functions

5.2 Lazy lists: An extended example

5.2.1 Memoizing lazy lists and avoiding recomputation

5.2.2 Helper functions for inspecting lazy lists

5.3 Separating program description from evaluation

5.4 Infinite lazy lists and corecursion

5.5 Conclusion

Summary

5.6 Exercise answers