Iterators, generators and resumable state

intermediateCommon atAnthropicOpenAIGoogleMetaRead firstClass design and invariantsRecursionPractise in the Sandbox →

An iterator hands out values one at a time through next(), remembering its position between calls. A generator is a function that writes that iterator for you: yield pauses it, the next next() resumes it. Chained generators form a lazy pipeline that does only the work the consumer asks for, in O(1) extra memory per stage. To checkpoint an iterator, its position must be plain data you can save and feed back in, which usually means writing the iterator as a class with explicit state rather than a generator.

The idea in plain words

A vending machine doesn’t hand you every snack at once. You press a button, you get one. The machine remembers which slot is next.

That’s an iterator. Two methods (or one, depending on language): “give me the next value” and “is there anything left?”. Everything else is hidden: the values might come from a list, a file, a network, or be computed on the spot.

Two consequences matter in interviews:

• Laziness. Nothing is computed until someone asks. Chain a reader, a parser, a filter and a take(3), and only enough input is read to produce three results. The rest is never touched.
• Position is state. “Where am I?” lives somewhere. In a generator, it’s hidden inside a paused function call. In a hand-written iterator class, it’s a few fields you can read, save to disk, and restore later. That second form is what “resumable” or “checkpointable” means.

Terms:

• Iterable: something you can ask for an iterator (a list, a range, a file). Iterator: the cursor itself.
• Generator: a function containing yield. Calling it returns an iterator and runs no code yet.
• Exhausted: the iterator has nothing left; Python raises StopIteration, JS returns { done: true }, C# MoveNext() returns false.

See it

Press next() and watch one value travel through the whole pipeline before the next one starts. Compare the work bars with eager mode, which builds every intermediate list first. Then save a checkpoint, crash, and resume: two integers were enough to rebuild the pipeline. Values produced after the checkpoint come out again, which is why resumable systems talk about “at least once”.

A lazy pipeline: source → map(x²) → filter(even) → take(n)

sandbox

source (≤ 14)take nevaluationlazy (generators)eager (lists)

next()save checkpointcrashresume from checkpoint↺

3

8

5

6

1

4

7

10

9

2

12

11

01234567891011

pos

idle: nothing runs until someone calls next()

work done by each stage

source read

0 / 12

map calls

0 / 12

filter calls

0 / 12

consumer received

nothing yet

pos0

taken0/3

statelive

Press next() a few times. Then switch to eager and compare the work bars.

When to reach for it

The problem says…	Why an iterator fits
“implement has_next() / next()”	That’s the iterator interface. Design the state, then the two methods.
“the input is huge / a stream / doesn’t fit in memory”	Lazy evaluation keeps O(1) items in memory per stage.
“flatten / interleave / merge these sequences on demand”	An iterator over iterators, with a small cursor state.
“save the position and resume later” / “after a restart”	Explicit, serializable state. Not a generator.
“skip ahead n items quickly”	Your state must allow jumping (known block sizes), not just stepping.
“first k results matching…”	A lazy pipeline with an early stop.

How it works

Generators in each language

	Python	TypeScript / JavaScript	C#
Define	def f(): ... yield x	function* f() { ... yield x; }	IEnumerable<T> F() { ... yield return x; }
Get the next value	next(it) (raises StopIteration at end)	it.next() → { value, done }	e.MoveNext() then e.Current
Loop	for x in it	for (const x of it)	foreach (var x in seq)
Lazy library ops	itertools: islice, chain, takewhile, generator expressions	write your own take / map, or iterator helpers in recent runtimes	LINQ: Where, Select, Take are all lazy
Stop early	return inside the generator	return (calls return() upstream)	yield break

1. Write each stage as a generator that takes an iterable and yields results. It holds at most one item at a time.
2. Compose them: take(filter(map(read(source)))). Composition runs nothing.
3. Drive the pipeline from the end: a for loop, list(...), or .ToList(). Each request pulls one item through every stage.
4. Stop early by stopping the consumer. Upstream stages simply never get asked again.

Python

slow_requests.py

from collections.abc import Iterable, Iterator
from itertools import islice

pulled = 0  # counts how many raw lines were actually read


def lines(text: str) -> Iterator[str]:
    global pulled
    for line in text.splitlines():
        pulled += 1
        yield line  # 1. pause here until the consumer asks for more


def parse(rows: Iterable[str]) -> Iterator[tuple[str, int]]:
    for row in rows:
        name, _, ms = row.partition(",")
        yield name, int(ms)  # 2. each stage pulls one item from the stage before it


def slow(reqs: Iterable[tuple[str, int]], limit: int) -> Iterator[str]:
    return (name for name, ms in reqs if ms > limit)  # generator expression: also lazy


if __name__ == "__main__":
    log = "home,12\nsearch,340\ncart,25\npay,900\nhome,8\nsearch,410"
    first_two = list(islice(slow(parse(lines(log)), 300), 2))  # 3. take(2) stops the chain
    assert first_two == ["search", "pay"]
    assert pulled == 4  # the last two lines were never read
    print("ok")

TypeScript

slow_requests.ts

import assert from "node:assert/strict";

let pulled = 0; // counts how many raw lines were actually read

function* lines(text: string): Generator<string> {
  for (const line of text.split("\n")) {
    pulled++;
    yield line; // 1. pause here until the consumer asks for more
  }
}

function* parse(rows: Iterable<string>): Generator<[string, number]> {
  for (const row of rows) {
    const [name, ms] = row.split(",");
    yield [name, Number(ms)]; // 2. each stage pulls one item from the stage before it
  }
}

function* slow(reqs: Iterable<[string, number]>, limit: number): Generator<string> {
  for (const [name, ms] of reqs) if (ms > limit) yield name;
}

function* take<T>(xs: Iterable<T>, n: number): Generator<T> {
  if (n <= 0) return;
  for (const x of xs) {
    yield x;
    if (--n === 0) return; // 3. returning ends the loop, which calls return() on the upstream generators
  }
}

const log = "home,12\nsearch,340\ncart,25\npay,900\nhome,8\nsearch,410";
const firstTwo = [...take(slow(parse(lines(log)), 300), 2)];
assert.deepEqual(firstTwo, ["search", "pay"]);
assert.equal(pulled, 4); // the last two lines were never read
console.log("ok");

C#

slow_requests.cs

int pulled = 0; // counts how many raw lines were actually read

IEnumerable<string> Lines(string text)
{
    foreach (var line in text.Split('\n'))
    {
        pulled++;
        yield return line; // 1. pause here until the consumer asks for more
    }
}

IEnumerable<(string Name, int Ms)> Parse(IEnumerable<string> rows)
{
    foreach (var row in rows)
    {
        var parts = row.Split(',');
        yield return (parts[0], int.Parse(parts[1])); // 2. each stage pulls from the one before
    }
}

var log = "home,12\nsearch,340\ncart,25\npay,900\nhome,8\nsearch,410";
// LINQ operators are lazy too: Where/Select/Take compose without running anything.
var query = Parse(Lines(log)).Where(r => r.Ms > 300).Select(r => r.Name).Take(2);
if (pulled != 0) throw new Exception("nothing should run before enumeration");
var firstTwo = query.ToList(); // 3. ToList drives the pipeline; Take(2) stops it early
if (!firstTwo.SequenceEqual(["search", "pay"])) throw new Exception("wrong result");
if (pulled != 4) throw new Exception($"expected 4 lines read, got {pulled}");
Console.WriteLine("ok");

Iterators you can checkpoint

A paused generator can’t be written to disk: its position is a suspended stack frame (Python’s pickle refuses generators; C# compiles yield return into a hidden class). When the spec says “save the position and resume”, write the iterator by hand.

1. Decide what the position is, as plain data: indexes, counters, a path. Make it the smallest thing that fully determines the next value.
2. Store only that in fields. next() reads the position, produces the value, advances the position.
3. state() returns a copy of those fields; a constructor (or set_state) accepts one and validates it.
4. Normalize the position after every step (for example, skip past empty chunks), so that two iterators at the same logical place always report the same state.

Python

fib.py

import json


class Fib:
    """Fibonacci numbers as an explicit-state iterator: its state is two ints and a count."""

    def __init__(self, state: dict[str, int] | None = None) -> None:
        s = state or {"a": 0, "b": 1, "n": 0}
        self.a, self.b, self.n = s["a"], s["b"], s["n"]  # 1. everything needed to continue

    def __iter__(self) -> "Fib":
        return self

    def __next__(self) -> int:
        value = self.a
        self.a, self.b, self.n = self.b, self.a + self.b, self.n + 1  # 2. advance the state
        return value

    def state(self) -> dict[str, int]:
        return {"a": self.a, "b": self.b, "n": self.n}  # 3. plain data: JSON-safe


if __name__ == "__main__":
    it = Fib()
    head = [next(it) for _ in range(5)]
    saved = json.dumps(it.state())  # 4. write the checkpoint somewhere durable
    rest = [next(it) for _ in range(3)]

    resumed = Fib(json.loads(saved))  # a new object, maybe in a new process
    assert [next(resumed) for _ in range(3)] == rest  # continues exactly where it stopped
    assert head == [0, 1, 1, 2, 3] and rest == [5, 8, 13]
    print("ok")

TypeScript

fib.ts

import assert from "node:assert/strict";

interface FibState { a: number; b: number; n: number }

/** Fibonacci numbers as an explicit-state iterator: its state is two numbers and a count. */
class Fib implements IterableIterator<number> {
  private s: FibState; // 1. everything needed to continue
  constructor(state: FibState = { a: 0, b: 1, n: 0 }) { this.s = { ...state }; }

  next(): IteratorResult<number> {
    const { a, b, n } = this.s;
    this.s = { a: b, b: a + b, n: n + 1 }; // 2. advance the state
    return { value: a, done: false };
  }

  [Symbol.iterator](): IterableIterator<number> { return this; }

  state(): FibState { return { ...this.s }; } // 3. plain data: JSON-safe
}

const it = new Fib();
const head = Array.from({ length: 5 }, () => it.next().value);
const saved = JSON.stringify(it.state()); // 4. write the checkpoint somewhere durable
const rest = Array.from({ length: 3 }, () => it.next().value);

const resumed = new Fib(JSON.parse(saved) as FibState); // a new object, maybe a new process
assert.deepEqual(Array.from({ length: 3 }, () => resumed.next().value), rest);
assert.deepEqual(head, [0, 1, 1, 2, 3]);
assert.deepEqual(rest, [5, 8, 13]);
console.log("ok");

C#

fib.cs

using System.Text.Json;

var it = new Fib();
var head = Enumerable.Range(0, 5).Select(_ => it.Next()).ToList();
var saved = JsonSerializer.Serialize(it.State); // 4. write the checkpoint somewhere durable
var rest = Enumerable.Range(0, 3).Select(_ => it.Next()).ToList();

var resumed = new Fib(JsonSerializer.Deserialize<FibState>(saved)); // new object, maybe new process
if (!Enumerable.Range(0, 3).Select(_ => resumed.Next()).SequenceEqual(rest)) throw new Exception("resume differs");
if (!head.SequenceEqual([0L, 1, 1, 2, 3]) || !rest.SequenceEqual([5L, 8, 13])) throw new Exception("values");
Console.WriteLine("ok");

record FibState(long A, long B, int N); // 3. plain data: JSON-safe

// Fibonacci numbers as an explicit-state iterator. A `yield return` method would hide this
// state inside a compiler-generated class that you cannot save or restore.
class Fib(FibState? state = null)
{
    public FibState State { get; private set; } = state ?? new FibState(0, 1, 0); // 1. all we need

    public long Next()
    {
        var (a, b, n) = State;
        State = new FibState(b, a + b, n + 1); // 2. advance the state
        return a;
    }
}

has_next without consuming

has_next() must not move the position. Either keep the position always pointing at a real next value (advance past empty parts eagerly, after each next()), or peek and cache the next value in a field. The first keeps the saved state clean; the second is simpler for wrapped iterators.

What it costs

	Time to first result	Total work for first k results	Extra memory
Eager lists (map → filter → slice)	O(n)	O(n), all stages, every item	O(n) per stage
Lazy generator pipeline	O(items until first match)	O(items until the k-th match)	O(1) per stage
Explicit-state iterator	same as lazy	same as lazy	O(size of the position)
Checkpoint / restore	—	O(size of the position) to save; restore may need O(skip) to re-seek	the saved state

Laziness has a cost: the same iterator can usually be consumed once. Iterating it a second time gives nothing. If you need the values twice, materialize them (list(...)) or re-create the pipeline.

Variations you’ll meet

• Flattening nested data. An iterator over nested lists keeps a stack of positions, one per level, instead of recursing.
• Peeking iterators. Wrap any iterator, cache one value, and expose peek().
• Merging sorted iterators. Keep the head of each in a heap; next() pops the smallest and refills from that source.
• Skip / seek. If you know the length of each block (a run in run-length encoding, a page of results), skip whole blocks with arithmetic instead of calling next() n times. That’s the difference between O(n) and O(blocks).
• Async iteration. async for (Python), for await (JS), IAsyncEnumerable<T> with await foreach (C#): same model, each next() may wait for I/O.
• Exactly once vs at least once. If the consumer’s side effects aren’t saved together with the checkpoint, a crash between them replays some items. Make consumers idempotent, or save both atomically.

Pitfalls

• Mutating the collection while iterating it. Python raises RuntimeError for dicts; .NET throws InvalidOperationException; JS Map keeps going in surprising ways. Iterate a copy, or collect changes and apply them after.
• Consuming an iterator twice. The second pass is empty, silently.
• has_next() that advances. Calling it twice skips a value.
• State that isn’t normalized. Pointing at an empty block means has_next() lies and saved states differ for the same position.
• Trusting a restored state. A state from disk can be out of range or stale. Validate it, and decide what an invalid state does (reject, or clamp).
• Generators that capture loop variables late. Python’s (lambda: i for i in ...) and JS closures can see the final value. Bind values explicitly.

In the interview

• Ask: “Can the source change while I iterate? Is it too big to load? Does the state need to survive a restart? What should next() do when exhausted: return null or throw?”
• Say what the position is before writing code, for example for a run-length decoder: “My state is (run index, offset within the run), always pointing at a real value or at the end.”
• State costs: “next() is amortized O(1): every empty run is skipped once.”
• Test the boundaries: empty input, all-empty parts, save at the very start and at the very end, restore then call has_next() twice.
• Expect follow-ups: nested input, skipping ahead fast, and concurrent consumers.

Check yourself

Check yourself

pick one

A pipeline is read_lines(file) → parse → filter → take(5). The file has 1,000,000 lines and the 5th match is on line 40. How many lines are read?

A1,000,000B40C5DIt depends on the filter selectivity only

Check yourself

pick one

You need to save an iterator's position to disk and resume after a restart. Why is a plain Python generator a poor fit?

AGenerators are slower than classesBIts position lives in a suspended frame that cannot be serialized; you need explicit stateCGenerators cannot yield integers

Check yourself

pick one

A run-length decoder over [(3, 'a'), (0, 'b'), (2, 'c')] stores (run, offset). After returning the third 'a', what should the state be?

A(0, 3)B(1, 0)C(2, 0), the next real valueDAny of these; they mean the same thing

Practice on your own

These are classic exercises, not gym questions:

• A peeking iterator: wrap any iterator and add peek() without losing values.
• A zigzag iterator over two lists: alternate values, continue with the longer one.
• A run-length decoder: iterate [(3, 'a'), (2, 'b')] as a a a b b, with skip(n) in O(runs).
• An in-order iterator over a binary search tree using an explicit stack, with O(h) memory.

Go deeper

• Python docs, Iterator types and itertools; PEP 255 introduced generators.
• MDN, Iterators and generators: the iteration protocols and function*.
• Microsoft Learn, yield statement and deferred execution in LINQ.
• Gamma et al., Design Patterns (1994): the Iterator pattern, external vs internal iteration.

Related

Streaming and online algorithmsProcessing input you can't hold in memory.

Class design and invariantsAn iterator's position is its invariant.

RecursionNested data: recursion vs an explicit stack.

Snapshots, backup and restoreCheckpointing a whole store, not a cursor.