Понимание необходимости функций-генераторов в JavaScript

Генераторы — это подкатегория итераторов в JavaScript¹.

Немного теории об итераторах

Итераторы в JavaScript тесно связаны с генераторами. Генераторы реализуют итеративный протокол простым в использовании способом. Но сам JS уже использует итерации различными способами, что делает генераторы применимыми напрямую.

Перечисление

В общем, итераторы обобщают перечисление вещей. Это может быть массив, и в этом случае разница минимальна:

const arr = [1, 2, 3, 4, 5];

for(let i = 0; i < arr.length; i++) { 
  const item = arr[i];
  console.info(`do something with ${item}`);
}

const arr = [1, 2, 3, 4, 5];

for(let it = arr[Symbol.iterator](), current = it.next(); !current.done; current = it.next()) { 
  const item = current.value;
  console.info(`do something with ${item}`);
}

Это немного запутанный способ сделать это, но это наглядный пример для непосредственного сравнения с обычным циклом for. В действительности вы бы использовали цикл for..of, который обрабатывает итерацию гораздо более удобным способом, если объект реализует итерируемый протокол:

const arr = [1, 2, 3, 4, 5];

for(const item of arr) { 
  console.info(`do something with ${item}`);
}

Однако протокол итерации позволяет перебирать произвольные данные. Например, мы можем создать связанный список (минимальный пример), который предоставляет итератор². Тогда для его просмотра можно использовать тот же for (const item of iterable), не разбираясь в реализации списка:

class Node {
  constructor (value, next = null) {
    this.value = value;
    this.next = next;
  }
}

class LinkedList {
  constructor(head) {
    this.head = head;
  }
  
  [Symbol.iterator]() {
    let next = this.head;
    return { 
      next() { 
        const current = next;
        next = current?.next;
        return {
          value: current?.value,
          done: current === null
        }
      }
    }
  }
}

const links = 
  new Node(1, 
    new Node(2, 
      new Node(3, 
        new Node(4, 
          new Node(5)))));

const list = new LinkedList(links);

for(const item of list) { 
  console.info(`do something with ${item}`);
}

То же самое можно сделать с другими реализациями списков или с деревьями, картами, множествами и т. д. Все они обрабатываются единообразно. В противном случае для каждого понадобится совершенно другая for петля.

Деструктуризация задания

Протокол итератора используется не только для циклического выполнения. Они также необходимы для так называемой деструктуризации массива. Он не только работает с массивами, но и использует итерируемый протокол для разрешения идентификаторов. Итак, вы можете использовать его с массивами:

const arr = [1, 2, 3, 4, 5];

const [a, b, ...rest] = arr;

console.info(a, b, rest);

или списки:

class Node {
  constructor (value, next = null) {
    this.value = value;
    this.next = next;
  }
}

class LinkedList {
  constructor(head) {
    this.head = head;
  }
  
  [Symbol.iterator]() {
    let next = this.head;
    return { 
      next() { 
        const current = next;
        next = current?.next;
        return {
          value: current?.value,
          done: current === null
        }
      }
    }
  }
}

const links = 
  new Node(1, 
    new Node(2, 
      new Node(3, 
        new Node(4, 
          new Node(5)))));

const list = new LinkedList(links);

const [a, b, ...rest] = list;

console.info(a, b, rest);

и так далее.

Синтаксис распространения

То же самое можно сказать и о синтаксисе распространения³. Он также опирается на итерации:

распространение массива в качестве аргументов:

function doMath(a, b, c, d, e) {
  return a + b + c + d + e;
}

const arr = [1, 2, 3, 4, 5];

console.info(doMath(...arr));

распространение списка в качестве аргументов:

class Node {
  constructor (value, next = null) {
    this.value = value;
    this.next = next;
  }
}

class LinkedList {
  constructor(head) {
    this.head = head;
  }
  
  [Symbol.iterator]() {
    let next = this.head;
    return { 
      next() { 
        const current = next;
        next = current?.next;
        return {
          value: current?.value,
          done: current === null
        }
      }
    }
  }
}

const links = 
  new Node(1, 
    new Node(2, 
      new Node(3, 
        new Node(4, 
          new Node(5)))));

const list = new LinkedList(links);

function doMath(a, b, c, d, e) {
  return a + b + c + d + e;
}

console.info(doMath(...list));

и так далее.

И другие обычаи

Итерации широко используются в JavaScript. Они поддерживают множество (на данный момент) базовых функций языка.

Однако, что еще более важно, они допускают различные способы итерации, которые могут даже обрабатывать бесконечные источники данных (например, чтение потока данных) или, возможно, даже читать очень большой набор данных (например, файл размером в гигабайты), требующий всего этого. сразу (например, взять чанк -> обработать -> взять другой чанк и т. д.).

Это можно сделать без итераторов. Однако не без необходимости каждый раз заново изобретать что-то близкое к итерируемому протоколу.

Генераторы

Генераторы в JavaScript создают итерации. Это делает их полезными для работы со всем, что обрабатывает итерируемый протокол. Например, генератор значительно упрощает создание итерируемого списка. От:

[Symbol.iterator]() {
  let next = this.head;
  return { 
    next() { 
      const current = next;
      next = current?.next;
      return {
        value: current?.value,
        done: current === null
      }
    }
  }
}

к гораздо более удобоваримому:

*[Symbol.iterator]() {
  let current = this.head;
  while(current !== null) {
    yield current.value;
    current = current.next;
  }
}

class Node {
  constructor (value, next = null) {
    this.value = value;
    this.next = next;
  }
}

class LinkedList {
  constructor(head) {
    this.head = head;
  }
  
  *[Symbol.iterator]() {
    let current = this.head;
    while(current !== null) {
      yield current.value;
      current = current.next;
    }
  }
}

const links = 
  new Node(1, 
    new Node(2, 
      new Node(3, 
        new Node(4, 
          new Node(5)))));

const list = new LinkedList(links);

for(const item of list) { 
  console.info(`do something with ${item}`);
}

Но более того, генераторы могут напрямую подключаться к любому существующему использованию итераций в JavaScript:

Перечисление:

function *generator() {
  yield 1;
  yield 2;
  yield 3;
  yield 4;
  yield 5;
}

for(const item of generator()) { 
  console.info(`do something with ${item}`);
}

Задание на деструктуризацию:

function *generator() {
  yield 1;
  yield 2;
  yield 3;
  yield 4;
  yield 5;
}

const [a, b, ...rest] = generator();

console.info(a, b, rest);

Синтаксис распространения:

function doMath(a, b, c, d, e) {
  return a + b + c + d + e;
}

function *generator() {
  yield 1;
  yield 2;
  yield 3;
  yield 4;
  yield 5;
}


console.info(doMath(...generator()));

Помимо прямого подключения к JavaScript, генераторы также являются сопрограммами, позволяющими приостанавливать и продолжать выполнение функций. Для этого есть два огромных преимущества:

Легко обрабатывать чрезвычайно большие или бесконечные потоки данных.

Я также читал, что функции-генераторы полезны для создания бесконечных потоков данных, таких как последовательность Фибоначчи. Однако я могу добиться того же результата, используя цикл while и две переменные.

Вы можете сделать это легко

function fibonacci() {
  let a = 0, b = 1;
  const result = [];
  result.push(a);
  result.push(b);
  while (true) {
    const next = a + b;
    result.push(next);
    a = b;
    b = next;
  }

  return result;
}

Проблема в том, что это бесполезная функция. Если его вызвать, это приведет к бесконечному выполнению. Хотя показанная функция генератора не будет⁴:

function* fibonacci() {
  let a = 0, b = 1;
  while (true) {
    yield a;
    const next = a + b;
    a = b;
    b = next;
  }
}

const fib = fibonacci();

console.info(fib.next().value);
console.info(fib.next().value);
console.info(fib.next().value);
console.info(fib.next().value);
console.info(fib.next().value);
console.info(fib.next().value);

Вариант без генератора необходимо будет изменить, чтобы он завершился, чтобы быть полезным. Но даже с этой модификацией существует несколько вариантов использования, каждое из которых потребует отдельной модификации:

• взятие n-го элемента потребует создания огромного массива практически бесплатно. Итак, функцию можно изменить так, чтобы она возвращала один элемент на n-й позиции, однако...
• ... если взять элементы от n до n+m, потребуется вернуть массив.
• возьмите кусок предметов, обработайте его, затем возьмите еще один кусок

Реализованный генератором Фибоначчи не нужно изменять, чтобы справиться с ними. С помощью пары помощников⁵ мы можем получить любое значение, которое нам действительно нужно:

function* skip(n, iterator) {
  for (let i = 0; i < n; i++) //skip n
    iterator.next();
    
  yield* iterator; //return the rest
}

function* take(n, iterator) {
  for (let i = 0; i < n; i++)
    yield iterator.next().value;
}


function* fibonacci() {
  let a = 0, b = 1;
  while (true) {
    yield a;
    const next = a + b;
    a = b;
    b = next;
  }
}

const fib = fibonacci();

//skip the first 10, take the next 5
const it = take(5, 
  skip(10, fib)
);

for(const item of it) {
  console.info(`do something with ${item}`);
}

Те же skip и take можно использовать в любой итерации. У нас могла бы быть какая-то функция генерации идентификаторов:

function* skip(n, iterator) {
  for (let i = 0; i < n; i++) //skip n 
    iterator.next();
    
  yield* iterator; //return the rest
}

function* take(n, iterator) {
  for (let i = 0; i < n; i++) 
    yield iterator.next().value;
}

function* idGenerator() {
  let i = 1;
  while (true) {
    yield `Some_random_id_${i}`;
    ++i;
  }
}

const idGen = idGenerator();

//skip the first 10, take the next 5
const it = take(5, 
  skip(10, idGen)
);

for(const item of it) {
  console.info(`do something with ${item}`);
}

Или даже объекты, реализующие iterable⁶ и другие итерируемые структуры:

function* skip(n, iterator) {
  for (let i = 0; i < n; i++) //skip n 
    iterator.next();
    
  yield* iterator; //return the rest
}

function* take(n, iterator) {
  for (let i = 0; i < n; i++) 
    yield iterator.next().value;
}

const arr = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", 
             "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"];

const arrayIterator = arr[Symbol.iterator]();

//skip the first 10, take the next 5
const it = take(5, 
  skip(10, arrayIterator)
);

for(const item of it) {
  console.info(`do something with ${item}`);
}

Существует множество очень универсальных помощников, которые можно использовать для любой итерации, а реализовать их в качестве генераторов очень просто⁵:

function* skip(n, iterator) {
  for (let i = 0; i < n; i++) //skip n 
    iterator.next();
    
  yield* iterator; //return the rest
}

function* take(n, iterator) {
  for (let i = 0; i < n; i++) 
    yield iterator.next().value;
}

function* map(mappingFn, iterator) {
  for (value of iterator)
    yield mappingFn(value);
}

function* filter(predicate, iterator) {
  for (value of iterator)
    if (predicate(value))
      yield value;
}

function* generator() {
  let i = 1;
  while (true) {
    yield i;
    ++i;
  }
}

const gen = generator();


//square the 2001th to 2006th even number
const it = map(x => x*x, 
  take(10, 
    skip(2000, 
      filter(x => x % 2 === 0, gen)
    )
  )
);


for(const item of it) {
  console.info(`do something with ${item}`);
}

Можете ли вы сделать то же самое с циклом? Конечно. Но вам придется переопределять его снова и снова для использования различных источников данных — массивов, карт, наборов, чтения файлов, получения значений из базы данных и т. д. Рассмотрим, например, случай попытки использования большого файла CSV: если вы хотите читать и обрабатывать построчно (загружая весь файл в память) можно. Но если он реализован как генератор, то его можно легко использовать с помощью чего-либо еще, использующего итераторы/генераторы:

//take 10 records that fulfil some criteria. 
//A CSV line has to be read and processed to calculate the data to filter on:
const data = take(10,
  filter(
      record => record.someCalculatedField === 42,
      map(
          line => convertToRecord(line),
          readCsvGeneratorFunction("some_file.csv")
      )
  );

Это тривиально, учитывая существующую инфраструктуру для обработки любых итераций/генераторов.

Самостоятельная реализация помощников вскоре вообще отпадет, поскольку помощники-итераторы скоро будут включены в основной язык. При использовании браузером эквивалентом будет следующее:

//square the 2001th to 2006th even number
const it = gen
    .filter(x => x % 2 === 0)
    .skip(2000)
    .take(10)
    .map(x => x*x);

//take 10 records that fulfil some criteria. 
//A CSV line has to be read and processed to calculate the data to filter on:
const data = readCsvGeneratorFunction("some_file.csv")
    .map(line => convertToRecord(line))
    .filter(record => record.someCalculatedField === 42)
    .take(10);

Однако в особых случаях все же может потребоваться введение нестандартного (для JavaScript, но, возможно, полезного для данного проекта) помощника-итератора.

async/await

Это может показаться удивительным, но async/await и генераторы неразрывно связаны:

• Генераторы — это функции, которые позволяют приостанавливать
• Асинхронные функции — это те, которые приостанавливаются в ожидании обещания.

Чтобы реализовать любой из них, вам, по сути, нужно реализовать оба. Основное требование — возможность приостанавливать и возобновлять выполнение функции.

Фактически, асинхронные функции можно реализовать как генераторы. Когда был выпущен ES2015 (ES6), генераторы были включены, но await был выпущен как часть ES2017. Между тем, обычным способом решения этой проблемы была транспиляция кода. Данный код типа:

async function foo() {
  await doAsyncStuff();
}

Если транспилировать с помощью TypeScript против ES2015, результат будет следующим:

"use strict";
var __awaiter = (this && this.__awaiter) || function (thisArg, _arguments, P, generator) {
    function adopt(value) { return value instanceof P ? value : new P(function (resolve) { resolve(value); }); }
    return new (P || (P = Promise))(function (resolve, reject) {
        function fulfilled(value) { try { step(generator.next(value)); } catch (e) { reject(e); } }
        function rejected(value) { try { step(generator["throw"](value)); } catch (e) { reject(e); } }
        function step(result) { result.done ? resolve(result.value) : adopt(result.value).then(fulfilled, rejected); }
        step((generator = generator.apply(thisArg, _arguments || [])).next());
    });
};
function foo() {
    return __awaiter(this, void 0, void 0, function* () {
        yield doAsyncStuff();
    });
}

Ссылка на игровую площадку

в то время как Бабель производит:

function asyncGeneratorStep(n, t, e, r, o, a, c) { try { var i = n[a](c), u = i.value; } catch (n) { return void e(n); } i.done ? t(u) : Promise.resolve(u).then(r, o); }
function _asyncToGenerator(n) { return function () { var t = this, e = arguments; return new Promise(function (r, o) { var a = n.apply(t, e); function _next(n) { asyncGeneratorStep(a, r, o, _next, _throw, "next", n); } function _throw(n) { asyncGeneratorStep(a, r, o, _next, _throw, "throw", n); } _next(void 0); }); }; }
function foo() {
  return _foo.apply(this, arguments);
}
function _foo() {
  _foo = _asyncToGenerator(function* () {
    yield doAsyncStuff();
  });
  return _foo.apply(this, arguments);
}

Ссылка на Babel

Оба опираются на генераторы, чтобы добиться того же, что и async/await.

¹ Также важные, но не связанные напрямую с генераторами: Протоколы итераций.

² Реализация намеренно немного многословна.

³ Когда не используется в литералах объектов, например, foo = { a: 1, ...bar }.

⁴ Если только код не попытается использовать все сразу. Что можно предотвратить. Это не для функции, не являющейся генератором, без изменения ее работы.

⁵Реализация намеренно упрощена. На самом деле им также следует проверять, не исчерпан ли итератор на каждом шаге. Это немного, но суть логики – это то, что важно. Поиск правильной реализации оставлен читателю в качестве упражнения. сравнить и сопоставить с полной реализацией без использования функций генератора.

⁶ Здесь для наглядности используется массив. Хотя arr.slice(n, n+m) можно использовать вместо take(m, skip(n, arr), первый все равно должен возвращать массив, который может быть огромным для больших значений m. При этом последнему не обязательно материализовать всю коллекцию сразу.