# 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 `println`

s 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.