Scala Streams — Lazy Sequences

Laziness in the language, before the collections

Two language features underpin everything here. A lazy val is computed on first access and then cached, with the initialisation guarded so concurrent first accesses compute it once. A by-name parameter, written def f(x: => Int), is not evaluated at the call site but re-evaluated every time the parameter is referenced in the body.

lazy val expensive = { println("computing"); 42 }
// nothing printed yet
expensive + expensive   // prints once, returns 84

def twice(x: => Int) = x + x
twice({ println("eval"); 21 })   // prints TWICE, returns 42

The distinction between those two -- cached versus recomputed -- is exactly the distinction between a LazyList and a view, one level up. A lazy collection is essentially a by-name tail plus, in the memoizing case, a lazy val holding the result.

The third piece is that laziness turns a value into a description of how to get a value. That is what allows an infinite sequence to exist as an ordinary object: nothing infinite is stored, only the rule for producing the next element and whatever prefix has been demanded so far.

LazyList

LazyList is the memoizing lazy sequence, introduced in Scala 2.13 to replace Stream. Its cons operator is #::, and both the head and the tail are lazy -- which is the specific improvement over the old Stream, whose head was evaluated eagerly. That difference is not academic: with a strict head, merely constructing a stream ran the first computation, which broke the cases where producing an element is expensive or can throw.

val naturals: LazyList[Int] = LazyList.from(0)
val squares  = naturals.map(n => n * n)
// nothing computed yet

squares.take(5).toList     // List(0, 1, 4, 9, 16) -- five elements computed

lazy val fibs: LazyList[BigInt] =
  BigInt(0) #:: BigInt(1) #:: fibs.zip(fibs.tail).map { case (a, b) => a + b }

fibs(100)   // 354224848179261915075

The Fibonacci definition is the canonical demonstration: a sequence defined in terms of itself, which terminates only because each element is computed at most once and cached. That memoization is what makes it linear rather than exponential -- the same definition with a non-memoizing structure would recompute the whole prefix at every step, and it is why this trick works for LazyList and not for a view.

Printing is deliberately non-forcing. A LazyList's string form shows computed elements followed by <not computed>, so inspecting one in a debugger or a log does not accidentally evaluate an infinite sequence. It also means the printed form is a picture of evaluation state rather than of contents, which is confusing exactly once.

Memoization is the feature and the hazard

Caching is what makes self-referential definitions and repeated traversal cheap, and it is also the reason LazyList is the type most likely to exhaust your heap.

The rule: a LazyList retains every element from the node you hold a reference to, onwards. Iterating a long or infinite lazy list while holding its head means the entire traversed prefix stays reachable and cannot be collected.

val huge: LazyList[Int] = LazyList.from(0)      // val -- the head is retained
huge.take(50000000).foreach(process)            // 50M cells now live: heap grows

def huge2: LazyList[Int] = LazyList.from(0)     // def -- a fresh head each call
huge2.take(50000000).foreach(process)           // prefix is collectable as it goes

The difference between those two is one keyword. With val the head is a field of the enclosing object and lives as long as it does; with def the head is a local that becomes unreachable as the traversal advances, so the garbage collector reclaims cells behind it.

The same hazard appears in less obvious forms: storing a lazy list in a field of a long-lived object, capturing it in a closure that outlives the traversal, or passing it to something that keeps it for logging. The rule of thumb worth remembering is that a LazyList longer than memory is safe to traverse and unsafe to hold, and if you cannot easily reason about who holds the head, you wanted an Iterator instead.

Views

A view is the non-memoizing form. Calling .view on a strict collection gives a lazy wrapper on which transformations build up a description; a terminal operation such as .toList or .foreach runs it.

val data = (1 to 1000000).toList

data.map(expensive).filter(_ > 0).take(10)          // maps ALL 1,000,000
data.view.map(expensive).filter(_ > 0).take(10).toList  // maps ~10-ish

The first line materialises a million-element intermediate list from the map, then another from the filter, then throws almost all of it away. The view version fuses the operations into a single pass and stops as soon as the take is satisfied, so it does a tiny fraction of the work and allocates no intermediates. That is the entire argument for views: avoiding intermediate collections and short-circuiting early exits.

The catch follows from the lack of memoization. A view re-runs its transformations on every traversal. Traverse it twice and every element function runs twice. If those functions have side effects, the side effects happen twice; if they are expensive, you pay twice. A view is also a window onto its underlying collection, so if that collection is mutable and changes, the view's contents change with it -- occasionally useful, more often a surprise.

The discipline that avoids all of this: build a view, use it once, force it immediately. Views are a pipeline optimisation, not a value to store or pass around. Returning a view from a public method is a reliable way to hand someone a correctness problem, because nothing in the type name warns them.

Iterators

An Iterator is lazy, non-memoizing and single-use. It holds a position and advances; once consumed it is spent, and consuming it again yields nothing.

That statefulness is the source of the classic error, which the compiler does not catch:

val it = source.getLines()
val count = it.size          // consumes the whole iterator
val first = it.next()        // NoSuchElementException -- it is empty now

In exchange, an iterator is the cheapest of the four: constant memory regardless of length, no per-element caching, no retained prefix. It is the correct type for streaming through data larger than memory -- lines of a file, rows from a result set, records from a socket -- and it is what the standard library's own file and I/O helpers return, for exactly that reason.

Iterators compose the same way collections do -- map, filter, flatMap, grouped, sliding, zip all return new lazy iterators -- and the composition is fused and single-pass. The rule is to derive one iterator chain and consume it exactly once, never branching two consumers off the same source, because both will interfere.

Choosing between the four

The two axes settle it. Ask whether elements should be computed up front or on demand, and whether computed elements should be remembered.

List, Vector and the other strict collections: everything computed, everything remembered. The default, and correct for anything that fits comfortably in memory and will be traversed more than once. Do not reach for laziness by reflex -- strict collections are faster per element and vastly easier to reason about.

LazyList: computed on demand, remembered. Use it for genuinely infinite or unbounded sequences, for self-referential definitions where memoization is the point, and for expensive elements that will be read more than once. Watch the head reference.

View: computed on demand, not remembered, reusable but recomputing. Use it to fuse a transformation chain over an existing collection where you would otherwise allocate intermediates, especially with an early exit. Force it immediately.

Iterator: computed on demand, not remembered, single-use. Use it for data larger than memory and for one-pass processing. Cheapest and least forgiving.

A decision heuristic that holds up: if the data does not fit in memory, Iterator. If it is infinite but you need memoization, LazyList. If it fits and you are just avoiding intermediates in one pipeline, .view. Otherwise a strict collection, which is most of the time.

Generating sequences

Beyond from and continually, the general constructor is unfold, which is the dual of a fold: it takes a seed and a function returning either the next element with a new state, or nothing to terminate.

// Collatz sequence from a starting value
def collatz(start: Int): LazyList[Int] =
  start #:: LazyList.unfold(start) {
    case 1 => None
    case n => val next = if (n % 2 == 0) n / 2 else 3 * n + 1
              Some((next, next))
  }

// paginated API as a lazy sequence of pages
def pages(first: String): LazyList[Page] =
  LazyList.unfold(Option(first)) {
    case None        => None
    case Some(token) => val p = fetch(token); Some((p, p.nextToken))
  }

The pagination case is the one that comes up constantly in real code, and it is worth noting what laziness buys there: the caller writes pages(start).flatMap(_.items).take(50) and exactly enough HTTP requests happen to produce fifty items. The paging logic and the consumption logic are completely decoupled, with no callback and no manual loop.

It is also where the interaction between laziness and effects becomes real, and the next section is about that.

Laziness and side effects

Mixing effects with lazy evaluation reliably produces surprises, and they fall into three shapes.

Effects happen later than the code reads. A map containing a print, a write or a request runs when the element is demanded, which may be in another method, after a return, or never. Reasoning about ordering by reading top to bottom stops working.

Effects happen more often than expected. On a view, every traversal re-runs them. Two traversals means two rounds of requests.

Exceptions surface at the wrong place. A failure inside an element computation is thrown at force time, so the stack trace points at the consumer, not at the construction site. Debugging this is materially harder than debugging strict code.

There is also a resource-lifetime trap specific to I/O: a lazy sequence derived from an open file or connection is only valid while that resource is open. Returning such a sequence from a method whose finally block closes the source produces something that fails on first use, and the pattern is common enough to be worth watching for -- pass a consuming function in, or force the result before closing.

Where effects are genuinely part of the pipeline -- retries, resource safety, concurrency, backpressure -- the standard-library lazy types are the wrong tool and the effectful streaming libraries in the ecosystem are the right one. They exist precisely because LazyList models 'values computed later' and not 'effects performed later', and conflating the two is what makes lazy I/O code fragile.

Memoized recursion — the one trick worth stealing

Because a LazyList caches by position, indexing into one is a memo table with no bookkeeping. That turns certain recursive definitions into dynamic programming for free.

// exponential: recomputes the whole subtree at every call
def slowFib(n: Int): BigInt =
  if (n < 2) n else slowFib(n - 1) + slowFib(n - 2)

// linear: each index computed once, then cached
lazy val fib: LazyList[BigInt] =
  BigInt(0) #:: BigInt(1) #:: fib.zip(fib.tail).map { case (a, b) => a + b }

// a memoized cost table over an input array
lazy val best: LazyList[Int] =
  LazyList.from(0).map { i =>
    if (i == 0) 0 else (1 to math.min(i, k)).map(j => best(i - j) + cost(i, j)).min
  }

The second and third definitions look self-referential and would not terminate with a strict collection, because building element i requires the list to already exist. Laziness resolves that: element i is only computed when demanded, and by then the earlier elements it refers to have been computed and cached.

Two cautions keep this from becoming a footgun. Indexing a LazyList is O(n) because it walks the cons cells, so a table accessed in random order is quadratic even though each element is computed once -- for that, an Array filled in order or an explicit memo map is the better structure. And the memo table is exactly the head-retention case from earlier, deliberately: you are holding the head on purpose, so the whole table stays live, which is fine for a bounded table and fatal for an unbounded one.

Used inside a single computation with a bounded index range, it is one of the tidiest expressions of dynamic programming available in the language.

Performance

Laziness is not free. Every element of a LazyList costs a cons cell plus a thunk plus the synchronisation of a lazy val, and traversal is pointer-chasing with poor locality. Against a Vector or an Array, the constant factor is substantial.

So laziness wins on the amount of work avoided, never on the speed of work performed. It pays when a short-circuit means most elements are never computed, when fusing avoids materialising large intermediates, when the sequence is unbounded and strictness is impossible, or when memoization turns an exponential recomputation into a linear one. It loses on small collections, on full traversals with cheap element functions, and anywhere the added indirection is not buying skipped work.

The measured version of this advice: on a few thousand elements with a cheap transformation, the strict version is typically faster than the view version despite doing more total work, because allocation of an intermediate list is cheaper than the per-element overhead of the lazy machinery. The crossover moves with element cost and collection size, so benchmark on your own data rather than assuming laziness is an optimisation.

Migration and pitfalls

Stream is deprecated; use LazyList. The replacement is nearly source-compatible -- the cons operator changed from #:: on Stream to the same operator on LazyList, and the head is now lazy -- but that head change alters evaluation timing, so code that relied on the first element being computed at construction behaves differently. That is almost always a fix rather than a regression.

Views changed meaning in 2.13. They are lazier and non-memoizing now; older code and older advice written against the previous behaviour can be misleading.

Do not call size, length or last on something infinite. Obvious when written down, easy to do accidentally through a logging statement or an assertion.

Beware force. It materialises the whole sequence, which on an unbounded one does not terminate.

Do not share an iterator. Two consumers of one iterator each get part of the data, silently.

Do not return views or iterators from public APIs without saying so loudly. Callers assume a collection is a value; both of these are one-shot or recomputing pipelines, and neither is safe to store.