bastianplsfix

← JavaScript + TypeScript

Iterator helpers

Iterators have methods. map, filter, take, drop, reduce, toArray, and several more, on every iterator in the language.

Two things make that more than a convenience. They are lazy: chaining them builds a description of work rather than doing any, and each element is pulled through the whole chain one at a time, so no intermediate arrays exist, ever. And they come from one shared prototype: Iterator is a real class, every built-in iterator inherits from Iterator.prototype, and so anything you can iterate gained these methods at once, including data structures that never had a map of their own.

There is a shift in habit here worth naming. Until now the advice was that you never see an iterator: you work with iterables through for-of and Array.from, and the walker stays hidden, which is how the whole iterables and iterators page operates until its last two steps. Now reaching for the iterator is the point, and knowing how to get hold of one matters.

Create programs/iterator-helpers.test.ts for this reference and keep it open. Start it with the assertion helpers used on this page:

import {
  assert,
  assertEquals,
  assertFalse,
  assertStrictEquals,
} from "@std/assert";

Follow the page as you add and revise the runnable examples below that import.

methods on the iterator, and they chain

Deno.test("methods on the iterator, and they chain", () => {
  const shouted = ["a", "b", "c"].values()
    .map((letter) => letter.toUpperCase())
    .toArray();

  assertEquals(shouted, ["A", "B", "C"]);
});
Check programs/iterator-helpers.test.ts
running 1 test from ./programs/iterator-helpers.test.ts
methods on the iterator, and they chain ... ok (1ms)

ok | 1 passed | 0 failed (1ms)

Three parts, and each is a choice. .values() gives you the array's iterator, which is the "getting hold of one" the intro promised. .map(...) is the transform, and it runs on the iterator rather than on the array. .toArray() collects the results, and that last step is a choice rather than a requirement, which the last step of this entry comes back to.

the middle of a chain stays an iterator

Deno.test("the middle of a chain stays an iterator", () => {
  assertEquals(
    [1, 2, 3, 4].values().filter((n) => n % 2 === 0).toArray(),
    [2, 4],
  );
  assertEquals(["a", "b", "c", "d"].values().take(2).toArray(), ["a", "b"]);
  assertEquals(
    ["a", "b", "c", "d"].values().drop(1).toArray(),
    ["b", "c", "d"],
  );
});
the middle of a chain stays an iterator ... ok (0ms)

map, filter, and flatMap do what their array namesakes do, except that each returns another iterator, which is why chains keep going. take and drop are new and have no array equivalent, and that absence tells you something: taking the first two of an array was always a slice, so take only earns its keep when the thing you are reading from might be long, or endless, and a later step feeds it exactly that.

the enders stop as soon as they know

Deno.test("the enders stop as soon as they know", () => {
  assert([1, 2, 3].values().some((n) => n > 2));
  assert([1, 2, 3].values().every((n) => n > 0));

  assertStrictEquals(["a", "b", "c"].values().find((_, i) => i === 1), "b");
  assertStrictEquals(
    ["a", "b", "c"].values().reduce((acc, v) => acc + v),
    "abc",
  );
});
the enders stop as soon as they know ... ok (0ms)

These end a chain rather than continuing it: some and every hand back a boolean, find hands back one value, and reduce folds everything into one result. some, every, and find stop as soon as they know the answer, and here that is free rather than an optimisation, for a reason the step nothing happens until something pulls measures: they simply stop pulling, and everything upstream stops being asked.

every callback receives a counter

Deno.test("every callback receives a counter", () => {
  const labelled = ["a", "b", "c"].values()
    .map((value, index) => `${index}:${value}`)
    .toArray();

  assertEquals(labelled, ["0:a", "1:b", "2:c"]);
});
every callback receives a counter ... ok (0ms)

The second callback parameter counts from zero, just as it does in the array methods. Worth one step of its own because an iterator has no indexes to look up: the counter is just how many values have come through so far, which happens to be the same number an array would have called the index.

Iterator.from turns an iterable into an iterator

Deno.test("Iterator.from turns an iterable into an iterator", () => {
  assertEquals(Iterator.from(new Set(["x", "y"])).toArray(), ["x", "y"]);
  assertEquals(Iterator.from("ab").toArray(), ["a", "b"]);
});
Iterator.from turns an iterable into an iterator ... ok (0ms)

Iterator.from takes an iterable and gives you an iterator with the methods on it. For built-in collections .values() is shorter and says more, so keep Iterator.from for the case in Iterator.from adapts something that only has next, where it does work nothing else can do.

nothing happens until something pulls

This is the step the entry exists for. A generator records every value it yields, the map callback records every value it transforms, and the log tells the truth about when work happens. The pipeline below is fully built, so predict the log:

Deno.test("nothing happens until something pulls", () => {
  const log: string[] = [];
  function* source(): Generator<string> {
    for (const value of ["a", "b", "c"]) {
      log.push(`yield ${value}`);
      yield value;
    }
  }

  const pipeline = source().map((value) => {
    log.push(`map ${value}`);
    return value.toUpperCase();
  });

  assertEquals(log, [
    "yield a",
    "map a",
    "yield b",
    "map b",
    "yield c",
    "map c",
  ]);

  assertStrictEquals(pipeline.next().value, "A");
  assertEquals(log, ["yield a", "map a"]);

  assertEquals(pipeline.toArray(), ["B", "C"]);
  assertEquals(log, [
    "yield a",
    "map a",
    "yield b",
    "map b",
    "yield c",
    "map c",
  ]);
});
Check programs/iterator-helpers.test.ts
running 6 tests from ./programs/iterator-helpers.test.ts
...
nothing happens until something pulls ... FAILED (8ms)

 ERRORS

nothing happens until something pulls => ./programs/iterator-helpers.test.ts:53:11
error: AssertionError: Values are not equal.

    [Diff] Actual / Expected

+   [
+     "yield a",
+     "map a",
+     "yield b",
+     "map b",
+     "yield c",
+     "map c",
+   ]
-   []

 FAILURES

nothing happens until something pulls => ./programs/iterator-helpers.test.ts:53:11

FAILED | 5 passed | 1 failed (9ms)

error: Test failed

The log is empty. That prediction was the array habit talking: arr.map(...) does all of its work on the line it is written, and this map did none of it. Building the pipeline built a description of work. Correct the first prediction to [], and the rest of the step, already written above, walks the pulls:

  1. pipeline.next() asks for one value, so the generator runs just far enough to push yield a and hand over "a", and the callback pushes map a and hands back "A". The log holds exactly one element's worth of work, ["yield a", "map a"], and nothing about "b" or "c" has happened.
  2. pipeline.toArray() pulls the rest, and the final log is interleaved the whole way down: yield b, map b, yield c, map c. There was never a moment when the yields ran as a batch, so there was never an array of unmapped values in memory.
nothing happens until something pulls ... ok (0ms)

Read that trace and both of the usual claims about laziness fall out of it. No intermediate arrays, because all the yielded values never existed together. And incremental processing, because the first result was available after one element's work rather than after all of it.

Compare the array version. arr.filter(...).map(...) builds a filtered array, then builds a mapped array, then hands you the second, and it does all of the filtering before any of the mapping. Fine for ten elements, not fine for a large file, and impossible for an endless source. It also explains why the enders stopping early is not a special case: they stop pulling, and everything upstream of them simply stops being asked.

the methods come from one shared prototype

Deno.test("the methods come from one shared prototype", () => {
  const arrayIterator = [].values();
  const arrayIteratorProto = Object.getPrototypeOf(arrayIterator);

  assertEquals(Reflect.ownKeys(arrayIteratorProto), [
    "next",
    Symbol.toStringTag,
  ]);
  assertStrictEquals(
    (arrayIteratorProto as Record<symbol, string>)[Symbol.toStringTag],
    "Array Iterator",
  );

  assertStrictEquals(
    Object.getPrototypeOf(arrayIteratorProto),
    Iterator.prototype,
  );
  assert(Object.hasOwn(Iterator.prototype, Symbol.iterator));
  assertStrictEquals(
    Object.getPrototypeOf(Iterator.prototype),
    Object.prototype,
  );

  function* generated(): Generator<string> {
    yield "a";
  }
  const genObj = generated();
  assert(genObj instanceof Iterator);
  assertEquals(genObj.map((v) => v + v).toArray(), ["aa"]);
});
the methods come from one shared prototype ... ok (0ms)

The step walks a chain of prototypes, and each link explains something:

  1. An array iterator's own prototype holds exactly two things, next and a Symbol.toStringTag of "Array Iterator". That is all an array iterator contributes: how to advance, and what to call itself.
  2. One level up sits Iterator.prototype, and that is where every helper lives. This is the answer to "how did all the iterators in the language gain methods at once": they did not each gain anything. One object gained the methods, and everything already inherited from it, by the mechanism the prototypes and inheritance page covers.
  3. Iterator.prototype also owns Symbol.iterator, which is the machinery behind a fact the iterables and iterators page pinned in an iterator is also an iterable, deliberately: every built-in iterator answers the protocol with itself.
  4. Its own prototype is Object.prototype, so the chain ends where every chain ends.

The generator at the bottom is the payoff: generator objects are in that chain too, so genObj instanceof Iterator holds and a generator you wrote gets the helpers for free. Producing with a generator and transforming with helpers is the natural division of labour, and it is available without any adapter.

a data structure gains operations it never had

Deno.test("a data structure gains operations it never had", () => {
  const numbers = new Set([-5, 2, 6, -3]);

  assertFalse("filter" in numbers);
  assertFalse("map" in numbers);

  assertEquals(numbers.values().filter((n) => n >= 0).toArray(), [2, 6]);
  assertEquals(
    new Set(numbers.values().map((n) => n / 2)),
    new Set([-2.5, 1, 3, -1.5]),
  );
});
a data structure gains operations it never had ... ok (0ms)

A Set has never had filter or map, and the first two assertions confirm it still does not. Going through its iterator supplies both. That is the practical reason this feature exists: every collection in the language and in the DOM that can be iterated now has the useful transformations available, without each one having to grow its own copy of them, and without the round trip through an array that used to be the answer.

Note the last assertion. new Set(...) accepts an iterable, the fact the iterables page filed under every consumer asks the same question, and a helper returns one, so the trip back to a Set costs nothing extra.

a helper reads the iterator you gave it

take sounds like it copies. The iterator below hands one element to take(1), so predict what is left:

Deno.test("a helper reads the iterator you gave it", () => {
  const once = ["a", "b", "c"].values();

  assertEquals(once.take(1).toArray(), ["a"]);
  assertEquals(once.toArray(), ["a", "b", "c"]);
  assertEquals(once.toArray(), []);

  const many = ["a", "b", "c"];
  assertEquals(many.values().take(1).toArray(), ["a"]);
  assertEquals(many.values().toArray(), ["a", "b", "c"]);
});
Check programs/iterator-helpers.test.ts
running 9 tests from ./programs/iterator-helpers.test.ts
...
a helper reads the iterator you gave it ... FAILED (8ms)

 ERRORS

a helper reads the iterator you gave it => ./programs/iterator-helpers.test.ts:127:11
error: AssertionError: Values are not equal.

    [Diff] Actual / Expected

    [
+     "a",
      "b",
      "c",
    ]

 FAILURES

a helper reads the iterator you gave it => ./programs/iterator-helpers.test.ts:127:11

FAILED | 8 passed | 1 failed (10ms)

error: Test failed

"a" is gone. Here is the trap, and it is the price of laziness: once.take(1) did not copy anything. It wrapped once, and consuming the wrapper consumed once, so the next read starts at "b", and the read after that gets nothing at all. No error, no warning, just fewer elements than you expected. Correct the prediction to ["b", "c"]:

a helper reads the iterator you gave it ... ok (0ms)

The array half of the step is unaffected because many.values() makes a fresh iterator each time it is called. That is exactly the distinction the iterables page measured in one-shot and reusable are both spelled Iterable, and helpers make it matter far more than it used to, because chaining is now the idiomatic thing to do and every chain has a single-use iterator at the bottom of it. The rule that follows: build a pipeline from a fresh iterator, and use it once. If you need the same data twice, either call .values() twice or materialise once with toArray and reuse the array.

Iterator.from adapts something that only has next

Deno.test("Iterator.from adapts something that only has next", () => {
  const legacyIterator = { next: () => ({ value: "#", done: false }) };

  assertFalse(legacyIterator instanceof Iterator);

  const adapted = Iterator.from(legacyIterator);

  assert(adapted instanceof Iterator);
  assertEquals(adapted.take(3).toArray(), ["#", "#", "#"]);
});
Iterator.from adapts something that only has next ... ok (0ms)

legacyIterator is a hand-written object with a next method and nothing else, which is a perfectly valid iterator by the protocol's rules and has none of the new methods, because it does not inherit from Iterator.prototype, and the first assertion measures exactly that. Iterator.from wraps it so that it does. This is the job the function is actually for: adapting iterators from libraries and older code, not fetching iterators from built-in collections.

Note the source is endless, the shape the iterables page called ordinary in an endless source is ordinary, and take(3) handles it without difficulty, because a lazy pipeline only ever asks for what it needs. The same source passed through an array method is not slow; it is impossible.

your own iterable can supply the methods

The iterables page built countdown with a hand-written next(). One line of difference makes its walker inherit every helper: give the returned object Iterator.prototype as its prototype. The checker, though, has opinions about the cast:

Deno.test("your own iterable can supply the methods", () => {
  const countdown = {
    from: 3,
    [Symbol.iterator](): IteratorObject<number, undefined> {
      let n = this.from;
      return {
        __proto__: Iterator.prototype,
        next(): IteratorResult<number> {
          return n > 0
            ? { value: n--, done: false }
            : { value: undefined, done: true };
        },
      } as IteratorObject<number, undefined>;
    },
  };

  const own = countdown[Symbol.iterator]();
  assert(own instanceof Iterator);
  assertEquals(own.map((n) => n * 10).toArray(), [30, 20, 10]);

  assertEquals([...countdown], [3, 2, 1]);
});
Check programs/iterator-helpers.test.ts
TS2352 [ERROR]: Conversion of type '{ __proto__: Iterator<any, any, any>; next(): IteratorResult<number>; }' to type 'IteratorObject<number, undefined, unknown>' may be a mistake because neither type sufficiently overlaps with the other. If this was intentional, convert the expression to 'unknown' first.
  Type '{ __proto__: Iterator<any, any, any>; next(): IteratorResult<number, any>; }' is missing the following properties from type 'IteratorObject<number, undefined, unknown>': map, filter, take, drop, and 10 more.
        return {
               ^
    at file:///programs/iterator-helpers.test.ts:155:16

error: Type checking failed.

Read the second line of that error: the literal is "missing" map, filter, take, drop, and 10 more. It is not missing them; it inherits all of them through the prototype we just assigned. The checker cannot see that, because TypeScript models __proto__: in an object literal as an ordinary property rather than as a prototype assignment, a corner the objects as dictionaries page measures in on Deno, __proto__ as a property is inert and the prototypes and inheritance page comes back to in the checker does not model an ad-hoc prototype. The error's own hint is the way out, and it is the double cast from the any, unknown, and never page's as is a claim, not a conversion: convert to unknown first.

        } as unknown as IteratorObject<number, undefined>;
      },
    };
your own iterable can supply the methods ... ok (0ms)

The runtime takes our side: own instanceof Iterator passes, the helpers work, and the object stays a reusable iterable, spreading to [3, 2, 1] on request. Two honest caveats ride along. The __proto__: key in an object literal is the one form of __proto__ that still sets a prototype on Deno, and the claim we signed with the cast is only true because that line is there. If either bothers you, a generator method, the shape the iterables page closed with in a generator method is a factory, not a one-shot, is the shorter answer and gets the helpers by inheritance with no cast at all.

a chain does not have to end in toArray

Deno.test("a chain does not have to end in toArray", () => {
  const collected: string[] = [];

  for (const line of ["a", "", "b"].values().filter((l) => l.length > 0)) {
    collected.push(line);
  }

  assertEquals(collected, ["a", "b"]);
});
a chain does not have to end in toArray ... ok (0ms)

A helper returns an iterator, an iterator is iterable, so for-of consumes the chain directly and nothing is ever materialised. Call toArray when you genuinely need an array, and not as punctuation.

In practice