skip to content

How does short-circuiting work with Sequences, and why does `asSequence().filter{}.first{}` avoid scanning the whole collection?

level: middleimportance: must knowfreq 65%

answer

  1. Pull model: one element through whole chain
  2. first/find/any/none/take stop early
  3. Eager filter scans all, then first reads result
  4. Infinite sequences need take/first to bound
  5. sorted/distinct buffer -> kill short-circuit

basics

~10 s

A Sequence pulls elements one by one. Terminal operations like first, find, take, and any stop the moment they have their answer, so the rest of the data is never touched.

solid answer

~40 s

Because a `Sequence` is lazy and processes elements vertically (one element through the whole chain at a time), a short-circuiting terminal operation can stop the iterator early. `first { predicate }` pulls elements through the upstream `filter`/`map` only until one satisfies the predicate, then returns. `take(n)` requests at most n elements and stops. `any`, `none`, `find`, `indexOfFirst` behave the same. With an eager `List`, `filter` first builds a full filtered list (touching every element) and only then does `first` look at the result — so no early exit upstream. This is the core reason `list.asSequence().filter{}.first{}` can be O(k) instead of O(n). It also enables operating on infinite sequences from `generateSequence`, where `take`/`first` are the only way to terminate.

code

kotlin · 3 lines
kotlin
val firstEven = (1..Int.MAX_VALUE).asSequence()
    .map { it * 3 }
    .first { it % 2 == 0 } // pulls only until first even, returns fast

go deeper

for a junior

Knows first/take stop early on a Sequence.

for a middle

Explains the pull model and contrasts with eager filter doing a full pass before first.

for a senior

Identifies stateful intermediate ops that defeat short-circuiting and orders the pipeline to preserve it.

for a principal

Reasons about algorithmic complexity (O(k) vs O(n)) and designs APIs returning Sequences to keep laziness composable.

## What short-circuiting means Short-circuiting is stopping iteration as soon as the result is determined, without examining remaining elements. It only helps when the pipeline is **lazy** end-to-end. ## The pull model A `Sequence` exposes an `Iterator`. Terminal operations drive that iterator with `hasNext()`/`next()`. Each `next()` pulls **one** element from the source and runs it through every intermediate stage (`map`, `filter`). The moment a short-circuiting terminal has its answer, it stops calling `next()` — upstream work simply never happens for the remaining elements. ## Short-circuiting terminal operations - `first()` / `first { }` — returns the first (matching) element. - `find { }` — like `firstOrNull { }`. - `take(n)` — actually an *intermediate* op that caps the stream; combined with a terminal it stops after n. - `any { }` — stops at the first match (returns true). - `none { }` — stops at the first match (returns false). - `indexOfFirst { }`, `firstOrNull()`. ## Eager contrast ```kotlin val data = (1..10_000_000) // Eager: filter scans ALL 10M, builds a list, THEN first reads index 0 val a = data.toList().filter { it > 5 }.first() // touches 10M // Lazy: pulls element 1 -> passes filter -> first returns. touches 1 val b = data.asSequence().filter { it > 5 }.first() // touches 1 ``` With eager operators each stage is a separate full pass, so `filter` cannot know that `first` only needs one element. ## Infinite sequences depend on this ```kotlin val firstThreeSquares = generateSequence(1) { it + 1 } .map { it * it } .take(3) .toList() // [1, 4, 9] ``` Without lazy short-circuiting, `generateSequence(1){ it + 1 }` would loop forever. `take(3)` plus a terminal op bounds it. ## Gotcha: stateful intermediate ops Some intermediate ops (`sorted`, `distinct` partly, `chunked`) must buffer or even consume the whole upstream before yielding, which defeats short-circuiting for stages downstream of them. Put `filter`/`take` before such operators when possible.

  • Does putting `sorted()` before `first()` in a Sequence still short-circuit?
    No. sorted() is a stateful intermediate op that must consume and buffer the entire upstream before emitting anything, so first() can't stop early.
  • Is take(n) a terminal or intermediate operation?
    Intermediate — it returns a Sequence. It caps the stream, but you still need a terminal op (toList/first) to actually run the pipeline.

saying these in an interview costs you the question

  • Saying eager filter().first() also short-circuits the filter
  • Not realizing sorted/distinct break short-circuiting
  • Calling take a terminal operation
  • Claiming any/none scan the whole sequence
  • Thinking infinite sequences can be materialized with toList directly

context

resolving links…