SyntaxPilot
Courses/JavaScript/Lesson 22
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

JavaScript · Lesson 22 of 40

Iterators and generators

queued

These are the notes for JavaScript episode 22. for...of happily walks arrays, strings, Sets and Maps, but crashes on your own object with TypeError: playlist is not iterable. You'll look inside for...of, find the iterator protocol ([Symbol.iterator](), next(), { value, done }), and build your own iterator by hand. Then you'll hit two problems: that's a lot of boilerplate, and arrays build every value up front (10 million squares just to use 3 cost hundreds of milliseconds and about 200 MB). The fix is the generator: a function* that yields one value at a time and pauses in between. Every output below is real Node.js output (node main.js); timings and memory will differ on your machine.

Builds on: loops and for...of (episode 6), arrays (7), objects (8), functions (9), closures (10), destructuring and spread (12), classes (16), Map and Set (21).

The real-life idea: the bank's token machine

A bank has a token machine at the door. Press the button and it prints the next token, one at a time, only when someone asks. At closing time it says clearly: that was the last one. The bank does not print a pile of a thousand tokens in the morning.

Token machine JavaScript
The machine at the door [Symbol.iterator](): how for...of finds the iterator
The button next()
A printed token { value: 3, done: false }
"That was the last one" { value: undefined, done: true }
Printing on demand, no pile a generator: values made only when asked (lazy)
Printing 10 million tokens at 9 am building a giant array up front (eager)

The problem: for...of refuses your own object

for (const x of [10, 20]) console.log("array", x);
for (const ch of "hi") console.log("string", ch);
for (const v of new Set(["chai"])) console.log("set", v);
const playlist = { songs: ["Monsoon", "Sunrise", "Old Delhi"] };
for (const song of playlist) console.log(song);
array 10
array 20
string h
string i
set chai
for (const song of playlist) console.log(song);
                   ^

TypeError: playlist is not iterable

Iterable means "something for...of can walk through". Arrays, strings, Sets, Maps (and arguments, typed arrays, NodeLists in the browser) are iterable. A plain object is not.

Looking inside for...of: the iterator

Before the loop starts, for...of asks the object for an iterator by calling its [Symbol.iterator]() method. Then it calls the iterator's next() again and again. Each call returns { value, done }; when done is true the loop stops.

const songs = ["Monsoon", "Sunrise"];
const it = songs[Symbol.iterator]();
console.log(it.next());
console.log(it.next());
console.log(it.next());
console.log(typeof {}[Symbol.iterator]);
{ value: 'Monsoon', done: false }
{ value: 'Sunrise', done: false }
{ value: undefined, done: true }
undefined

So for (const s of songs) { ... } is roughly:

const it = songs[Symbol.iterator]();
let step = it.next();
while (!step.done) {
  const s = step.value;
  // ... loop body ...
  step = it.next();
}

Symbol.iterator is a symbol: a special, unique key that can never clash with an ordinary key like "songs" or "name". JavaScript uses well-known symbols like this for its own machinery so that your keys and its keys never mix.

Why the playlist failed: a plain object has no [Symbol.iterator] method, so for...of has nobody to ask.

The fix, version 1: write an iterator by hand

The iterator protocol is an agreement: an object is iterable if it has a [Symbol.iterator]() method that returns an object with a next() method, and next() returns { value, done }.

const tokens = {
  from: 1,
  to: 4,
  [Symbol.iterator]() {
    let current = this.from;
    const last = this.to;
    return {
      next() {
        if (current <= last) return { value: current++, done: false };
        return { value: undefined, done: true };
      }
    };
  }
};
for (const t of tokens) console.log("Token", t);
console.log([...tokens]);
const [first, second] = tokens;
console.log(first, second);
Token 1
Token 2
Token 3
Token 4
[ 1, 2, 3, 4 ]
1 2
  • [Symbol.iterator]() { ... } is a method with a computed key (the key is the value of Symbol.iterator).
  • current lives in a closure (episode 10), so each next() call remembers where it was.
  • for...of, spread [...x], array destructuring, Array.from(x), new Set(x), new Map(x) and Promise.all(x) all use this same protocol.

The next problem: boilerplate, and everything up front

The hand-written iterator works but needs a method, a closure, a second object and two returns. And arrays have a bigger cost: they hold every value at once.

const before = process.memoryUsage().heapUsed;
const t = Date.now();
const squares = [];
for (let i = 1; i <= 10000000; i++) squares.push(i * i);
console.log(squares.slice(0, 3));
const mb = (process.memoryUsage().heapUsed - before) / 1e6;
console.log(Date.now() - t, "ms,", Math.round(mb), "MB");
[ 1, 4, 9 ]
258 ms, 198 MB

process.memoryUsage().heapUsed is how many bytes of memory your program's objects are using. A quarter of a second and ~200 MB for three numbers. And some sequences (order numbers, IDs, sensor readings) never end, so they can't be arrays at all.

Why: arrays are eager: every value is computed and stored before you use any. We want lazy values: made only when asked, like the token machine.

The fix, version 2: generators

A generator function is written function* (a star after function). Inside it, yield value hands out a value and pauses the function right there.

  • Calling a generator function runs none of its body. It returns a generator object.
  • Each gen.next() runs the body until the next yield, returns { value, done: false }, and pauses.
  • When the function ends (or returns), next() returns { value: undefined, done: true }.
  • A generator object is an iterator and is iterable, so for...of, spread and destructuring work on it.
function* counter() {
  console.log("  start");
  yield 1;
  console.log("  after 1");
  yield 2;
  console.log("  after 2");
}
const gen = counter();
console.log("created");
console.log(gen.next());
console.log(gen.next());
console.log(gen.next());
created
  start
{ value: 1, done: false }
  after 1
{ value: 2, done: false }
  after 2
{ value: undefined, done: true }

created prints first: creating the generator ran nothing. Each next() resumes exactly where the last yield paused.

range, endless IDs, endless squares

function* range(from, to) {
  for (let i = from; i <= to; i++) yield i;
}
console.log([...range(1, 4)]);

function* orderIds() {
  let id = 1001;
  while (true) yield "ORD-" + id++;
}
const ids = orderIds();
console.log(ids.next().value, ids.next().value);

function* squares() {
  for (let i = 1; ; i++) yield i * i;
}
for (const sq of squares()) {
  if (sq > 50) break;
  console.log(sq);
}
[ 1, 2, 3, 4 ]
ORD-1001 ORD-1002
1
4
9
16
25
36
49

while (true) is safe inside a generator because it pauses at every yield. Never spread an endless generator ([...orderIds()] never finishes): take values with next() or a loop with break.

Making the playlist iterable: *[Symbol.iterator]() and yield*

const playlist = {
  songs: ["Monsoon", "Sunrise", "Old Delhi"],
  *[Symbol.iterator]() {
    yield* this.songs;
  }
};
for (const song of playlist) console.log("Now playing:", song);
console.log([...playlist].length);
Now playing: Monsoon
Now playing: Sunrise
Now playing: Old Delhi
3
  • *[Symbol.iterator]() is a generator method (the star goes before the method name; in a class too).
  • yield* iterable yields every value of another iterable, one by one (delegation).

Two extras worth knowing

function* g() { const got = yield "question"; console.log("got", got); }
const q = g(); console.log(q.next().value); q.next("answer");
function* h() { try { yield 1; yield 2; } finally { console.log("cleanup"); } }
for (const v of h()) { console.log(v); break; }
question
got answer
1
cleanup
  • next(x) sends x back in: it becomes the result of the paused yield.
  • break out of for...of calls the generator's return(), so finally blocks run (good for cleanup).

Common mistakes (and what really happens)

You wrote What happens Why Fix
for (const s of playlist) on a plain object TypeError: playlist is not iterable no [Symbol.iterator] method add *[Symbol.iterator](), or loop playlist.songs / Object.values(playlist)
function range() { ... yield i; } SyntaxError: Unexpected identifier 'i' yield is only a keyword inside function* function* range()
const r = range(1, 3); [...r]; [...r] [ 1, 2, 3 ] then [] a generator is used up after one pass call range(1, 3) again
const g = counter(); expecting logs nothing prints calling only creates the generator g.next() or loop over it
[...orderIds()] on an endless generator never finishes (then out of memory) spread collects everything next() or a loop with break
next() returning a plain value return 5 for...of breaks with TypeError: Iterator result 5 is not an object next() must return { value, done } return { value: 5, done: false }
A huge array just to read the first few hundreds of ms and MB arrays are eager a generator

Mini project: paging through orders

A shop shows orders 3 per page. A generator hands out one page at a time:

function* pages(items, size) {
  for (let i = 0; i < items.length; i += size) {
    yield items.slice(i, i + size);
  }
}
const orders = ["ORD-1", "ORD-2", "ORD-3", "ORD-4", "ORD-5", "ORD-6", "ORD-7"];
let page = 1;
for (const p of pages(orders, 3)) {
  console.log(`Page ${page++}:`, p.join(", "));
}
Page 1: ORD-1, ORD-2, ORD-3
Page 2: ORD-4, ORD-5, ORD-6
Page 3: ORD-7

Try it: stop after page 2 with break, or show the next page each time the user presses Enter (episode 14's stdin).

Practice

  1. Write a generator evens() that never ends, and print the first 5 values.
  2. Make a Classroom class whose objects can be looped over with for...of, giving each student.
  3. Write take(iterable, n) that returns an array of the first n values of any iterable (even an endless one).
  4. Write a generator for the Fibonacci numbers (0, 1, 1, 2, 3, 5...) and print the first 10.
Solutions

1.

function* evens() {
  for (let n = 0; ; n += 2) yield n;
}
const out = [];
for (const e of evens()) {
  if (out.length === 5) break;
  out.push(e);
}
console.log(out);
[ 0, 2, 4, 6, 8 ]

2.

class Classroom {
  constructor(...students) {
    this.students = students;
  }
  *[Symbol.iterator]() {
    yield* this.students;
  }
}
const room = new Classroom("Asha", "Ravi", "Meena");
for (const s of room) console.log("Present:", s);
console.log([...room]);
Present: Asha
Present: Ravi
Present: Meena
[ 'Asha', 'Ravi', 'Meena' ]

3.

function take(iterable, n) {
  const result = [];
  if (n <= 0) return result;
  for (const x of iterable) {
    result.push(x);
    if (result.length === n) break;
  }
  return result;
}
function* naturals() { for (let i = 1; ; i++) yield i; }
console.log(take(naturals(), 4), take("hello", 2), take([1, 2], 5));
[ 1, 2, 3, 4 ] [ 'h', 'e' ] [ 1, 2 ]

4.

function* fibonacci() {
  let [a, b] = [0, 1];
  while (true) {
    yield a;
    [a, b] = [b, a + b];
  }
}
const fib = fibonacci();
console.log(Array.from({ length: 10 }, () => fib.next().value));
[
  0, 1,  1,  2,  3,
  5, 8, 13, 21, 34
]

Quick quiz

What does this print?

function* g() { yield "a"; yield "b"; }
const s = g();
console.log(s.next().value + s.next().value + s.next().done);
  • A. abtrue
  • B. abfalse
  • C. aundefinedtrue
  • D. ab
Answer

A. The first two next() calls give "a" and "b". The third runs off the end of the function, so done is true.

Interview questions

  • What is the difference between an iterable and an iterator?
  • What does for...of do step by step? What does Symbol.iterator do?
  • Why is a plain object not iterable? Name three ways to loop over an object anyway.
  • What does next() return? When is done true?
  • What is a generator? How is it different from a normal function?
  • What does yield do? What does yield* do?
  • Why can a generator contain while (true) safely?
  • What is lazy vs eager evaluation? When does laziness save memory?
  • Why does spreading the same generator twice give an empty array the second time?
  • What happens to a generator when you break out of a for...of loop over it?

Glossary

Term Meaning Example
Iterable something for...of (and spread) can walk; it has [Symbol.iterator]() arrays, strings, Sets, Maps
Iterator an object with next() that hands out values one at a time songs[Symbol.iterator]()
Iterator protocol the agreement: [Symbol.iterator]() returns an object whose next() returns { value, done } the tokens object
next() asks an iterator for the next value it.next()
{ value, done } an iterator result: the item, and whether it's finished { value: 1, done: false }
Symbol a unique key that can't clash with ordinary string keys Symbol.iterator
Symbol.iterator the well-known symbol for...of uses to get an iterator obj[Symbol.iterator]()
Computed key an object key written in [ ], using a value [Symbol.iterator]() { }
Eager all values computed and stored up front an array of 10 million squares
Lazy values computed only when asked a generator
Generator function a function* that can pause at yield function* range() { }
Generator object what a generator function returns; an iterator and iterable const gen = counter()
yield give out a value and pause yield i
yield* yield every value of another iterable yield* this.songs
Generator method a method written with a star *[Symbol.iterator]() { }
Exhausted (used up) an iterator that has returned done: true and stays done the second [...r] is []
process.memoryUsage() Node.js: how much memory the program uses .heapUsed in bytes

Summary

  • for...of asks an object for an iterator through [Symbol.iterator]() and calls next() until done is true.
  • A plain object isn't iterable; follow the iterator protocol and it becomes iterable for for...of, spread and destructuring.
  • Arrays are eager: every value is stored up front, which wastes memory and can't be endless.
  • Generators (function* + yield) pause and resume, make values on demand, and are iterators already.
  • *[Symbol.iterator]() { yield* ... } makes any object or class iterable in a few lines.
  • A generator is used up after one pass; calling it runs nothing until next(); yield needs the star.

Next episode: Regular expressions. How do you check that a phone number, a PIN code or an email has the right shape, without fifty if statements?