Chapter 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 if you had a deck of cards and you 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 in the following code:[1]

1 We’re now using the Scala standard library’s List type here, where map and filter are methods on List rather than standalone functions like the ones we wrote in chapter 3.

scala> List(1,2,3,4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3)

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.

5.1. Strict and non-strict functions

5.2. An extended example: lazy lists

5.3. Separating program description from evaluation

5.4. Infinite streams and corecursion

5.5. Summary