Lazy sequences in the Scala standard library

One way to learn the idioms and idiosyncrasies of a programming language is to follow the development of its standard library. The Scala standard libary, for example, deprecated its data structure for lazy sequences Stream and replaced it with a new data structure called LazyList in the 2.13 release. However, LazyList has different laziness characteristics than Stream, which recently sparked some discussion on GitHub. I found the discussion quite interesting and will try to illustrate the difference between both data structures in this post.

Stream

This is a simplified version of the definition of Stream:

class Stream[A](hd: A, tl: => Stream[A]) {
    val head: A = hd
    lazy val tail: Stream[A] = tl
    def apply(i: Int): A = if (i == 0) head else tail(i - 1)
}

A Stream consists of cons cells with an eagerly evaluated head and a lazily evaluated tail. When a Stream object is instantiated with expressions for the head and tail, only the head expression is immediately evaluated, whereas the tail is only evaluated when it is first accessed. Therefore, a Stream always looks like the following. All cons cells have an evaluated head, and all cons cells except the last one have an evaluated tail pointing at the next cons cell.

[  head, tail--]-->[  head, tail--]-->[  head, UNEVALUATED  ]

One way to construct such a stream is to use a recursive function. By injecting some printlns we can see in what order the function calls and the expressions for the head and the tail are evaluated. #:: is syntactical sugar for creating a Stream cons cell:

def mkStream(i: Int): Stream[Int] = {
    println(s"Evaluating cell $i")

    { println(s"Evaluating head for cell $i"); i } #:: { println(s"Evaluating tail for cell $i"); mkStream(i + 1) }
}

We can now force the evaluation of a few cons cells and observe the output.

val stream = mkStream(0)
println()
stream(1)
println()
stream(2)

The output is:

Evaluating cell 0
Evaluating head for cell 0

Evaluating tail for cell 0
Evaluating cell 1
Evaluating head for cell 1

Evaluating tail for cell 1
Evaluating cell 2
Evaluating head for cell 2

As you can see, the head of each cell is evaluated when the cell is constructed, but the tail is only evaluated to access the next cell.

LazyList

This is a simplified version of the definition of LazyList, the replacement for Stream:

class LazyList[A](hd: => A, tl: => LazyList[A]) {
    lazy val (head, tail): (A, LazyList[A]) = (hd, tl)
    def apply(i: Int): A = if (i == 0) head else tail(i - 1)
}

Now both head and tail are lazily evaluated. Therefore, the actual cons cell is only constructed when either head or tail are accessed. Interestingly (and maybe confusingly), both head and tail are always evaluated together. For example, accessing the head of an unevaluated LazyList cons cell will construct the cons cell and also evaluate its tail. Thus, LazyList structures look like this:

[  head, tail--]-->[  head, tail--]-->UNEVALUATED

With a recursive function to construct a LazyList similar to the one shown above for Stream and equivalent accesses to the individual cons cells, we get the following output:

Evaluating cell 0

Evaluating head for cell 0
Evaluating tail for cell 0
Evaluating cell 1
Evaluating head for cell 1
Evaluating tail for cell 1
Evaluating cell 2

Evaluating head for cell 2
Evaluating tail for cell 2
Evaluating cell 3

The first call to construct the LazyList evaluates neither the head nor the tail. In that sense, LazyList is lazier than Stream. However, evaluating the third cons cell (containing the 2) also invokes the function to construct the next cons cell. Here, LazyList is less lazy than Stream.

Conclusion

One immediate conclusion refers to porting uses of Stream to LazyList. To exploit laziness in LazyList in its current (Scala 2.13.2) version, it has to be used differently than Stream. If you are using a recursive function to construct the LazyList, make sure that you do the work in the expressions for head and tail, as these are lazily evaluated. Everything you do in the function outside of these expressions will the evaluated as soon as the previous cons cell is evaluated, even if only the head of that previous cons cell is accessed. So, for example, instead of

def mkLazyList(i: Int): LazyList[Int] = {
    val content = doExpensiveCalculation(i)
    content #:: mkLazyList(i + 1)
}

do

def mkLazyList(i: Int): LazyList[Int] = {
    doExpensiveCalculation(i) #:: mkLazyList(i + 1)
}

or

def mkLazyList(i: Int): LazyList[Int] = {
    lazy val content = doExpensiveCalculation(i)
    content #:: mkLazyList(i + 1)
}

At the time of this writing, a pull request for making the tail of a LazyList cons cell lazy again has been opened.