Iterator: walking a collection without knowing its insides

  • Lesson 24 of 32
  • 11 min
  • Intermediate
  • 13 steps

If your loop knows that users come in pages, every internal change forces you to edit it. You will hide those insides behind an iterator, make your class work with `for…of` and see where you already use this idea.

Values handed over
—
Requests to the API
—
Your codeititPagedMapfetchPages()rlUsersArrayListPagedIteratorprotocolIteratorAPIAPIReportnested forpages insideYour loop knows the pagesconst users = new Paged([["ana", "leo"], ["sol"]]);▸for (const page of users.pages)for (const u of page)show(u);edit itedit this toonow: users.byIdPaged changes inside−for (const page of users.pages)−for (const u of page)+for (const u of users.byId.values())show(u);next(){ value, done }The Iterator protocolinterface Iterator<T> {▸next(): IteratorResult<T>;}// { value: "ana", done: false }// { value: undefined, done: true }next()knows where it isnext(), step by stepconst it = users[Symbol.iterator]();▸it.next(); // {value:"ana",done:false}it.next(); // {value:"leo",done:false}it.next(); // {value:"sol",done:false}▸it.next(); // {value:undefined,done:true}no pagesyield* pagePaged becomes iterableclass Paged<T> implements Iterable<T> {constructor(private pages: T[][]) {}+*[Symbol.iterator]() {+for (const page of this.pages)+yield* page;+}}▸for (const u of users) show(u);has [Symbol.iterator]the same for…ofIterables you already havefor (const c of "sol") {} // s, o, lfor (const [k, v] of map) {} // pairsconst copy = [...new Set([1, 2])];▸for (const x of {}) {}▸// TypeError: {} is not iterable1 of 3 pagesfetches on demandPages fetched as you goasync function* fetchPages(total) {for (let p = 1; p <= total; p++)yield await getPage(p);}for await (const page of fetchPages(3)) {show(page);▸break; // only page 1 was fetched}one line per turnbreak closes rlreadline: one line per turnconst rl = readline.createInterface({input: fs.createReadStream(file),crlfDelay: Infinity,});▸for await (const line of rl) {show(line);}__next__()__iter__()The same protocol in Pythonclass Users:def __init__(self, items):self.items = itemsdef __iter__(self):yield from self.itemsit = iter(Users(["ana"]))next(it) # "ana"▸next(it) # StopIteration[...it] gives []already walked itA spent iteratorconst it = users[Symbol.iterator]();[...it]; // ["ana", "leo", "sol"]▸[...it]; // [][...users]; // all 3 againthe list changedConcurrentModificationExceptionJava: changing while walkingfor (String u : list) {if (u.equals("leo"))▸list.add("eva");}▸// ConcurrentModificationExceptiondo not write itan array will doWhen not, and what it costsan array or built-in will dodo not write your ownyou need items[5] or the totalan iterator gives neithervalues computed on requestharder to debugfor await over an APIhides the waitnext() or donefor…ofIterator in one tableproblemthe loop knows the insidessolutionnext() gives { value, done }in JS[Symbol.iterator] + generatorlazyfetches only what the loop askscarefulone use; no changes while walking
  • request
  • response
  • slow request
  • failed request

Step 1 of 13

Problem

Your loop knows about the pages

Your app keeps users in a Paged class that groups them in pages: [["ana", "leo"], ["sol"]]. To show them, your code walks users.pages and, inside, each page: two nested loops.

It works, but your loop knows how the collection is stored inside. That detail is none of its business: it only wanted the users, one after another.

What changed

  • two loops over users.pages

Step 2 of 13

Problem

Change the insides, change every loop

Now the team decides to keep users in a Map by id, users.byId. users.pages is gone and your loop breaks.

Not only yours: the report and every place that walked users has to be edited. An internal change to Paged became a change for everyone who uses it.

What changed

  • pages → byId
  • every loop, edited

Step 3 of 13

Concept

An object that hands you the next one

The idea of Iterator: instead of reaching into the collection, you ask it for an object that walks it for you. Gamma, Helm, Johnson and Vlissides list it among the behavioral patterns of their 1994 book: access the elements in order without exposing how they are stored.

In JavaScript that object follows a protocol with one method, next(), which returns { value, done }: the next value, or done: true when none are left.

What changed

  • the iterator it
  • the Iterator protocol

Step 4 of 13

Technique

next(), step by step

You get the iterator with users[Symbol.iterator]() and call next(). The first time it returns { value: "ana", done: false }; then "leo" and "sol". The fourth call returns { value: undefined, done: true }.

The iterator remembers where it is: it knows that page 1 ends after "leo" and jumps to page 2. The caller sees 3 values and an end, no pages.

What changed

  • it.next() × 4

Step 5 of 13

Solution

for…of makes the calls for you

You do not have to call next() by hand. If Paged has a [Symbol.iterator]() method, it is iterable: for…of gets the iterator, calls next() on every turn and stops at done: true.

The shortest way to write it is a generator, function* with yield: each yield hands over one value and pauses the function until the next next(), and yield* page hands over each page's values one by one. Your loop becomes for (const u of users).

What changed

  • *[Symbol.iterator]()
  • the nested loops

Step 6 of 13

Concept

You already use it: Array, String, Map and Set

Array, String, Map and Set already have their [Symbol.iterator](): that is why for…of walks the characters of a string or the [key, value] pairs of a Map. Spread ([...x]) and array destructuring use the same protocol.

A plain object {} does not have it, and in Node for (const x of {}) throws TypeError: {} is not iterable. Knowing the protocol explains that error: the object is missing [Symbol.iterator].

What changed

  • Paged → Map

Step 7 of 13

Technique

Lazy: pages from an API

An iterator does not need everything in memory: it fetches or computes each value when the loop asks for it. With async function* each turn can wait for a request, and for await waits for each page before going on.

In the example, fetchPages(3) could fetch 3 pages, but the loop leaves with break after the first one: the API gets 1 request out of 3. That is why a generator can be infinite: Iterator helpers such as take(5) also pull only what they need.

What changed

  • async function* fetchPages
  • API

Step 8 of 13

Technique

Where you meet it: reading a file in Node

Node.js's readline module reads a file line by line with the same protocol: you create the interface over a stream and walk it with for await (const line of rl). You do not get an array with every line: you get one per turn.

If you leave the loop with break, the docs say the interface is closed. It is the same for await as in the previous step: the source changed from an API to a file and your loop did not notice.

What changed

  • API
  • fetchPages → rl

Step 9 of 13

Concept

In Python: __iter__ and __next__

Python has the same protocol under other names: the iterable defines __iter__(), which returns the iterator, and the iterator defines __next__(), which returns the next value or raises StopIteration when none are left.

As in JavaScript, a generator (yield) implements the protocol for you. And one rule from the docs: an iterator that has raised StopIteration must keep raising it on every later call.

What changed

  • [Symbol.iterator] → __iter__
  • next() → __next__

Step 10 of 13

Trade-off

An iterator is used once

An iterable can be walked many times: each for…of asks for a new iterator. An iterator cannot: once it reached done: true, it stays there.

If you keep it, walk it, and then hand it to the report, [...it] gives [], with no error at all. Pass the iterable (users), not the iterator, or create a new one for each walk.

What changed

  • the report uses the same it

Step 11 of 13

Problem

Do not change the list while you walk it

In Java, if you add an element to an ArrayList while walking it with a for, the iterator's next step throws ConcurrentModificationException. Its iterators are fail-fast: they fail as soon as they notice a structural change they did not make.

The docs make clear this is best-effort: it is not guaranteed to catch every case, so do not write code that relies on the exception. If you need to remove elements while walking, do it through the iterator itself (it.remove()) or build a new list.

What changed

  • Paged → ArrayList
  • list.add() inside the for

Step 12 of 13

Trade-off

When not to write your own

If your data already is an array, a Map or any built-in, do not write an iterator: they already have one. And if you need access by position (items[5]) or the total before you start, an iterator gives you neither.

What you pay when you do use it: it is consumed once, values computed on request are harder to inspect while debugging, and a for await hides the wait of each request inside a loop that looks ordinary.

Step 13 of 13

Summary

Ask for the next one, never look inside

When a loop knows how a collection is stored, every internal change breaks whoever walks it. An iterator hands over the next value with next(), or done: true, and the loop sees nothing else.

In JavaScript a [Symbol.iterator]() written as a generator is enough to make your type work with for…of, and async function* fetches data in parts. An iterator is used once, and the collection is not changed while you walk it.

You will learn

  • See why walking a collection's insides ties your loop to how it is stored.
  • Use the protocol: `next()` returns `{ value, done }`.
  • Make your type work with `for…of` by writing a generator.
  • Fetch data in parts with `async function*` and `for await`.
  • Avoid walking the same iterator twice and changing a collection while you walk it.