Map

Пример предыдущего урока крайне просто обобщить до функции высшего порядка map. Напомню, что map — отображение. Если раньше мы отображали плоские списки, то теперь отобразим вложенную структуру. С точки зрения семантики ничего не меняется. map каждому узлу ставит в соответствие новый узел, так что структура всего дерева остаётся прежней, а вот данные внутри узла меняются.

const dfs = (tree) => {
  // Получаем имя узла и его детей.
  const [name, children] = tree;
  // Приводим имя узла к нижнему регистру.
  const newName = name.toLowerCase();
  // Если узел не содержит детей,
  // возвращаем его с изменённым именем.
  if (!children) {
    return [newName];
  }
  // Вызываем функцию dfs для каждого ребёнка
  // и возвращаем узел с изменённым именем и детьми.
  return [newName, children.map(dfs)];
};

const tree = ['A', [
  ['B', [['E'], ['F']]],
  ['C'],
  ['D', [['G'], ['J']]],
]];

JSON.stringify(dfs(tree));
// '["a", [["b", [["e"], ["f"]]], ["c"], ["d", [["g"], ["j"]]]]]'

https://repl.it/@hexlet/js-trees-map-dfs

Преобразование включает в себя следующие шаги:

  1. Переименовать функцию в map;
  2. Добавить в сигнатуру функции передачу функции обработчика;
  3. Пропустить ноду через эту функцию;

Mapping
Trees

// В коде используются два разных map. Один самописный, другой на массиве. 
const map = (f, tree) => {
  // Извлекаем детей из узла.
  const [, children] = tree;
  // Применяем к узлу переданную функцию
  // и извлекаем имя изменённого узла.
  const [newName] = f(tree);
  // Если узел не содержит детей
  // возвращаем его с изменённым именем.
  if (!children) {
    return [newName];
  }
  // Возвращаем узел с именем и детьми,
  // для каждого из которых вызывается
  // наша функция map
  return [newName, children.map((c) => map(f, c))];
};

const tree = ['A', [
  ['B', [['E'], ['F']]],
  ['C'],
  ['D', [['G'], ['J']]],
]];

// Вызываем map и передаём в неё функцию,
// которая приводит имя узла к нижнему регистру.
const mappedTree = map(([name]) => [name.toLowerCase()], tree);

JSON.stringify(mappedTree);
// '["a", [["b", [["e"], ["f"]]], ["c"], ["d", [["g"], ["j"]]]]]'

https://repl.it/@hexlet/js-trees-map-map

При дестракчеринге можно игнорировать отдельные элементы массива (выбирать конкретные значения с учётом порядка). В примере выше мы никак не использовали константу name, то есть в этом случае нам нужно только второе значение массива, поэтому выражение const [name, children] = tree; можно переписать так: const [, children] = tree;, не создавая тем самым лишнюю константу.

Дерево до отображения:

//   A *
//    /|\
// B * C * D
//  /|   |\
// E F   G J

Дерево после отображения:

//   a *
//    /|\
// b * c * d
//  /|   |\
// e f   g j

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

Если структура дерева изменится, то эту функцию придётся переписать, но общая схема останется прежней.

Мы учим программированию с нуля до стажировки и работы. Попробуйте наш бесплатный курс «Введение в программирование» или полные программы обучения по Javascript, PHP, Python и Java.

Хекслет

Подробнее о том, почему наше обучение работает →