Scala LazyList (was Stream), in depth: the cell model, what forces evaluation, exceptions and memoization, corecursion, paging with unfold and stack depth

The model: a chain of suspended cells

Think of a LazyList as a chain of cells. Each cell starts as a thunk, a piece of code that has not run yet. When something needs to know what the cell holds, the thunk runs once and its result is stored: either the empty list, or a head value plus a reference to the next cell, which is itself an unrun thunk. Unlike Stream, LazyList does not even know whether it is empty until its first cell is forced. The API documentation calls this being lazy in its head.

The cons operator #:: takes both its head and its tail by name, so writing a #:: rest captures the expressions without evaluating either. That one property is what makes self-referential definitions legal, as the Hamming example later shows. The string form makes the model visible: unevaluated cells print as <not computed>, and printing never forces anything, so a log line cannot accidentally evaluate an infinite list.

Watching it evaluate, and what changed from Stream

The first excerpt counts how many times the mapping function runs. Building the mapped list runs it zero times. Taking three elements runs it three times, and taking the same three again runs it zero more times, because those cells are now memoized. The second half constructs a Stream and a LazyList with side-effecting maps and checks which heads ran.

var calls = 0
def square(n: Int): Int = { calls += 1; n * n }
val squares = LazyList.from(1).map(square)
println(s"built: $squares, calls=$calls")
println(s"take(3): ${squares.take(3).toList}, calls=$calls")
println(s"after:  $squares")
squares.take(3).toList
println(s"again: calls=$calls (memoized)")

var hits = 0
val s = Stream.from(1).map { n => hits += 1; n }       // deprecated since 2.13.0
val l = LazyList.from(1).map { n => hits += 100; n }
println(s"Stream head ran: ${hits % 100}, LazyList head ran: ${hits / 100}")

The output, shown in full after the stack-depth section, confirms each step: calls=0 after construction, calls=3 after the first take, still 3 after the second, and a printed form of LazyList(1, 4, 9, <not computed>). Stream ran its first mapping during construction and LazyList ran none. That eager head was Stream's main flaw: a pipeline that should describe work started doing it, and an expensive or failing first element hit at definition time. The compiler warns that Stream is deprecated since 2.13.0 and points to LazyList; migration is mostly mechanical, and the main behavioural change is exactly this later evaluation.

What is lazy and what forces

Because every cell is a thunk, an operation is lazy if it can produce its result cell by building new thunks, and strict if it has to look at every element before it can return. That rule predicts the API without memorising it.

Three subtleties are worth knowing. take(n) is lazy and so is drop(n), but take(n).toList forces exactly n cells, which is the normal way to finish a pipeline. A filter over an infinite list with no matches never returns, because forcing its first cell keeps searching. knownSize is the safe way to ask about size: it returns -1 for an unevaluated list instead of walking it. Strict collections such as List do all their work up front, and the cost of choosing between strict and lazy structures is measured in Scala collections performance.

Exceptions, memoization and threads

Memoization holds only for success. If a cell's thunk throws, the exception propagates to whoever forced the cell and nothing is stored, so the next access runs the thunk again. The excerpt below uses LazyList.continually with a thunk that fails twice and then succeeds.

var attempts = 0
val flaky = LazyList.continually {
  attempts += 1
  if (attempts < 3) throw new RuntimeException(s"attempt $attempts") else attempts
}
for (_ <- 1 to 3) {
  try println(s"head = ${flaky.head} after $attempts attempts")
  catch { case e: RuntimeException => println(s"threw: ${e.getMessage}") }
}

It prints threw: attempt 1, threw: attempt 2, then head = 3 after 3 attempts. That behaviour is useful, because a transient failure is not frozen into the list forever, and dangerous, because a thunk with side effects such as a network call or a counter increment may run more times than you expect. Keep thunks pure where you can, and put retries in an explicit layer rather than relying on re-forcing.

Concurrent forcing is handled by the library: a cell that two threads force at once is evaluated once and both see the same result. In the 2.13.16 library each cell's state is a lazy val, whose initialisation is synchronized; the current development sources use compare-and-set instead, so depend on the outcome, not the mechanism. Laziness is not concurrency, though. A LazyList pipeline runs on whichever thread forces it, and a slow thunk blocks that thread. The general theory of by-name parameters and lazy val, which LazyList is built from, is in Scala lazy evaluation.

Corecursion: a list defined by itself

Corecursion builds a structure outward from a seed, where recursion consumes one. LazyList makes corecursive definitions natural because a cell's tail can refer to cells that do not exist yet. Hamming numbers, the numbers whose only prime factors are 2, 3 and 5, are the classic case: the sequence is 1 followed by the sorted merge of itself times 2, times 3 and times 5.

def merge(a: LazyList[BigInt], b: LazyList[BigInt]): LazyList[BigInt] = {
  val (x, y) = (a.head, b.head)
  if (x < y) x #:: merge(a.tail, b)
  else if (y < x) y #:: merge(a, b.tail)
  else x #:: merge(a.tail, b.tail)
}
lazy val hamming: LazyList[BigInt] =
  BigInt(1) #:: merge(hamming.map(_ * 2), merge(hamming.map(_ * 3), hamming.map(_ * 5)))
println(s"hamming: ${hamming.take(15).toList.mkString(" ")}")
println(s"hamming(1690) = ${hamming(1690)}")

The program printed 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 and hamming(1690) = 2125764000. It works because of memoization: each of the three scaled lists reads cells of hamming that have already been computed, so producing the nth number costs a constant amount of work and the whole prefix costs linear time. A non-memoizing structure such as a view would recompute the prefix for every element. The lazy val matters too: it lets the definition refer to itself, and #:: delays the reference until the first cell exists. Note that merge reads a.head eagerly, which is safe here because both inputs are infinite; on finite inputs you would check isEmpty first.

Worked example: paging an API with unfold

A practical use of LazyList is turning a cursor-paginated API into a sequence that fetches pages only when a consumer reaches them. LazyList.unfold takes a seed and a function returning either None, to stop, or the next element and the next seed. Here the seed is the cursor, and fetchPage stands in for an HTTP call that returns three items and a next cursor until the eight items run out.

var requests = 0
def fetchPage(cursor: Int): (List[String], Option[Int]) = {
  requests += 1                                   // stands in for an HTTP call
  val items = (cursor until math.min(cursor + 3, 8)).map(i => s"item$i").toList
  (items, if (cursor + 3 < 8) Some(cursor + 3) else None)
}
val pages: LazyList[List[String]] = LazyList.unfold(Option(0)) {
  case Some(c) => val (items, next) = fetchPage(c); Some((items, next))
  case None    => None
}
val items = pages.flatten
println(s"first 4: ${items.take(4).toList}, requests=$requests")
println(s"all: ${items.size} items, requests=$requests")

The output reads first 4: List(item0, item1, item2, item3), requests=2, and then all: 8 items, requests=3. Taking four items fetched exactly two pages; asking for the size fetched the last page and no more. Because the list memoizes, iterating items a second time costs no requests, which is what you want for a small result set reused several times and exactly what you do not want for millions of rows, since every page stays in memory while anything holds the head. For large exports, build the same unfold as an Iterator, which forgets as it goes, or use a streaming library with resource safety and back-pressure such as FS2.

Stack depth

Lazy structures move recursion from definition time to forcing time, and that is where the stack can overflow. The excerpt checks three cases.

println(LazyList.from(1).filter(_ % 1000000 == 0).head)       // sparse filter: fine
println(LazyList.from(1).knownSize)                           // -1: unknown, nothing forced

var deep = LazyList.empty[Int]
for (i <- 1 to 100000) deep = deep.lazyAppendedAll(LazyList(i))  // left-nested appends
try println(deep.head)
catch { case _: StackOverflowError => println("deep.head: StackOverflowError") }

The sparse filter found 1,000,000 without trouble, because filter skips non-matching elements in a loop inside one cell rather than through nested calls. knownSize returned -1 and forced nothing. The last case overflowed. Appending in a loop builds a left-nested chain: to find the head of the final list, the library must ask the list before it, which asks the one before that, a hundred thousand levels deep. The API documentation warns about exactly this: repeatedly chaining appends can overflow the stack when the result is forced. Build such lists right-nested instead, with #:: prepends, a single flatten over a list of parts, or a builder, and keep append inside a loop for strict collections.

The program&#x27;s complete output

All fragments above are excerpts of one program compiled with Scala 2.13.16 and run on JDK 23. Running it printed:

built: LazyList(<not computed>), calls=0
take(3): List(1, 4, 9), calls=3
after:  LazyList(1, 4, 9, <not computed>)
again: calls=3 (memoized)
Stream head ran: 1, LazyList head ran: 0
threw: attempt 1
threw: attempt 2
head = 3 after 3 attempts
hamming: 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24
hamming(1690) = 2125764000
first 4: List(item0, item1, item2, item3), requests=2
all: 8 items, requests=3
1000000
-1
deep.head: StackOverflowError

Failure modes

• Out of memory from a held head: a val, a field or a closure keeps the first cell alive, so every evaluated cell after it stays reachable.
• Hanging on infinite input: size, last, sum, a foreach without take, or a filter or find that never matches.
• Repeated side effects: a thunk that throws is re-run on the next access, so a failing network call inside one is retried by whoever touches it.
• Stack overflow at force time: left-nested appends or deeply nested non-tail recursion inside thunks.
• Accidental equality checks: comparing two infinite lazy lists with == never returns.
• Stream semantics assumed: code ported from Stream that expected the head to be evaluated at construction now evaluates later, so side effects move.

When to use something else

Choose LazyList when you need laziness and reuse: a sequence defined in terms of itself, a cached expensive prefix read more than once, or a pure infinite generator. Choose Iterator when you traverse once and want memory to stay flat. Choose a view to fuse a chain of transformations over an existing strict collection without intermediate copies, and force it immediately. Choose an effect-aware stream library when elements come from I/O, need resource cleanup, or must respect back-pressure. Laziness is a tool for controlling when work happens; it does not make the work cheaper.

What to do next

1. Search your code for Stream, replace it with LazyList, and look for side effects whose timing moves because the head is now lazy.
2. For each LazyList held in a val or field, confirm the prefix it retains is small, or switch to a def, an Iterator or a streaming library.
3. Make every thunk pure, and move retries and I/O into an explicit layer.
4. End every infinite pipeline with take, takeWhile or a find that is guaranteed to match, and use knownSize instead of size for checks.
5. Replace append-in-a-loop on lazy lists with prepends, flatten or a builder, and add a test that forces a long instance.
6. Write one small counting test, like the excerpts here, for any pipeline whose cost matters, so a future change that forces too early fails loudly.