skip to content

Explain, in terms of the lazy evaluation model, why a List chain allocates intermediate collections and a Sequence chain does not. How many intermediate lists does each create for filter→map→take?

level: middleimportance: should knowfreq 50%

answer

  1. List op = new List returned each time
  2. filter→map→take eager = 3 intermediate lists
  3. Sequence = wrapper objects, 0 intermediate lists
  4. FilteringSequence / TransformingSequence / TakeSequence
  5. sorted/distinct/chunked buffer (stateful) — exceptions

basics

~20 s

Each List operator returns a brand-new list, so filter→map→take makes three intermediate lists. A Sequence just wraps the previous step lazily and pushes elements one by one, so it makes zero intermediate lists until the terminal collector.

solid answer

~40 s

Eager collection operators are defined to return a new `List` each call: `filter` returns the filtered list, `map` returns the mapped list, `take` returns the truncated list. So `list.filter{}.map{}.take(n)` allocates three intermediate lists (plus any final). Sequences instead return lightweight wrapper `Sequence` objects (e.g. `FilteringSequence`, `TransformingSequence`, `TakeSequence`) that hold a reference to upstream and apply the transform lazily inside their iterator's `next()`. No element storage is created for intermediate stages; values flow element-at-a-time and only a terminal like `toList()` allocates one output collection. So the sequence chain creates **zero** intermediate lists. This is the core allocation argument for sequences on long chains over large inputs.

code

kotlin · 12 lines
kotlin
// Eager: 3 intermediate Lists materialized
val eager = (1..1000).toList()
    .filter { it % 2 == 0 }   // List #1
    .map { it * it }          // List #2
    .take(5)                  // List #3

// Lazy: 0 intermediate Lists; only toList() allocates output
val lazy = (1..1000).asSequence()
    .filter { it % 2 == 0 }   // FilteringSequence
    .map { it * it }          // TransformingSequence
    .take(5)                  // TakeSequence
    .toList()

go deeper

for a junior

Understands List ops make new lists and sequences avoid that, even without exact counts.

for a middle

Gives the correct counts (3 vs 0) and names the wrapper/lazy mechanism.

for a senior

Distinguishes stateless from stateful operators and knows sorted/distinct/chunked buffer.

for a principal

Reasons about heap/GC impact at scale and when allocation savings actually dominate runtime versus per-element lambda/iterator overhead.

## Eager: a new list per operator Standard-library extension functions on `Iterable<T>` are eager. Their contract: do the work now, return a concrete `List<R>`. ```kotlin val result = source .filter { it > 0 } // allocates intermediate List #1 .map { it * 2 } // allocates intermediate List #2 .take(10) // allocates intermediate List #3 ``` For `filter → map → take`, that's **3 intermediate lists**. Each is fully populated before the next operator starts. On large inputs this is real heap pressure and GC work, even when `take(10)` only needs ten results. ## Lazy: wrappers, not storage `asSequence()` switches every operator to a lazy variant. Internally these are tiny wrapper classes that store a reference to the upstream sequence and the lambda — for example `FilteringSequence`, `TransformingSequence` (for `map`), and `TakeSequence`. They allocate **no per-element storage**. ```kotlin val result = source.asSequence() .filter { it > 0 } // returns a FilteringSequence wrapper .map { it * 2 } // returns a TransformingSequence wrapper .take(10) // returns a TakeSequence wrapper .toList() // the ONLY allocation of a result list ``` **0 intermediate lists.** The wrappers form a chain of iterators; `toList()` pulls elements, each flowing through filter→map→take, and `take` stops the pull at 10. ## How the wrappers work (pull model) Each wrapper's `iterator().next()` calls its upstream's `next()`, applies its transform/predicate, and returns. `filter`'s iterator loops upstream until it finds a passing element; `map`'s applies the function; `take`'s counts and stops. Nothing is buffered. ## Caveat — stateful operators A few sequence operators are **stateful** and *do* buffer: `sorted`, `distinct`, `groupingBy`-style aggregation, `chunked`. `sorted` must read all elements to order them, breaking laziness at that point. The zero-allocation claim holds for stateless operators (`map`, `filter`, `take`, `drop`).

  • Does asSequence() itself copy the source data?
    No. It returns a Sequence view backed by the original Iterable's iterator; no copy is made.
  • Which common sequence operator breaks the zero-buffer property?
    Stateful ones like sorted, distinct, and chunked must read/store elements, so they buffer and partially break laziness.

saying these in an interview costs you the question

  • Claiming sequences allocate an intermediate list per operator
  • Saying eager filter→map→take allocates only one list
  • Believing sorted on a sequence stays fully lazy
  • Thinking asSequence() eagerly copies the collection

context

resolving links…