Понимание Array.prototype.reduce() и рекурсии на примере яблочного пирога

У меня были проблемы с пониманием reduce( ) и рекурсии в JavaScript, так что я написал эту статью чтобы объяснить их в первую очередь себе (эй, смотрите, это же рекурсия!). Эти концепции имеют некоторые сходства с приготовлением яблочного пирога. Я очень надеюсь вы сочтёте мои примеры как полезными так и аппетитными.

Дан массив содержащий вложенные массивы:

var arr = [1, [2], [3, [[4]]]]

Как результат мы хотим получить:

var flat = [1, 2, 3, 4]

Использование цикла for и оператора if.

Если мы знаем максимальное количество вложенных массивов, с которыми нам предстоит работать (в примере их 4), то нам вполне подойдёт цикл for для итерации по каждому элементу массива, а затем оператор if, чтобы проверить является ли этот элемент сам по себе массивом, и так далее…

function flatten() {
    var flat = [];
    for (var i=0; i<arr.length; i++) {
    if (Array.isArray(arr[i])) {
        for (var ii=0; ii<arr[i].length; ii++) {
        if (Array.isArray(arr[i][ii])) {
            for (var iii=0; iii<arr[i][ii].length; iii++) {
            for (var iiii=0; iiii<arr[i][ii][iii].length; iiii++) {
                if (Array.isArray(arr[i][ii][iii])) {
                flat.push(arr[i][ii][iii][iiii]);
                } else {
                flat.push(arr[i][ii][iii]);
                }
            }
            }
        } else {
            flat.push(arr[i][ii]);
        }
        }
    } else {
    flat.push(arr[i]);
    }
    }
}

// [1, 2, 3, 4]

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

Использование reduce.

К счастью у JavaScript есть пару методов для того чтобы сделать наш код понятнее и проще. Один из таких методов reduce( ). И выглядеть это всё будет вот так:

var flat = arr.reduce(function(done,curr){
    return done.concat(curr);
}, []);

// [ 1, 2, 3, [ [ 4 ] ] ] 

Получилось куда меньше кода, но мы пропускаем некоторые (в нашем примере один) вложенные массивы. Давайте вместе пошагово разберём как работает reduce ( ) и посмотрим что же он всё-таки делает, чтобы исправить это.

Array.prototype.reduce()

Метод reduce() применяет функцию к аккумулятору и каждому значению массива (слева-направо), сводя его к одному значению. (MDN)

Это не так сложно, как кажется. Давайте поговорим о reduce ( ) как о чём-то вне работы разработчика. Знакомьтесь, это Адам. Основная функция Адама состоит в том, чтобы взять яблоки из кучи, помыть их, а затем поместить одно за другим в корзину. Эта корзина блестящих яблок предназначена для того, чтобы стать вкусными яблочными пирогами. Это очень важная работа.

Яблоки + Человеческие усилия = Пирог. Не путайте формулу с рецептом яблоко-человеческого пирога, он не столь вкусный.

В приведённом выше примере куча яблок — это наш массив arr. Корзина — это переменная done, аккумулятор. Начальным значением done является пустой массив, который мы видим как [] последним параметром нашего reduce( ). Яблоко, которое Адам в данный момент моет — это curr (от current). Как только Адам заканчивает мыть текущее яблоко он кладёт его в корзину (мы делаем это с помощью .concat( ) ). Когда гора яблок заканчивается Адам отдаёт корзину с чистыми яблоками нам и идёт домой к своему коту.

Использование reduce( ) рекурсивно для обращения к вложенным массивам.

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


Прелестные, слегка перекошенные яблоки просто хотят быть любимыми / съеденными.

Вот что мы хотим от нашей яблоко-обрабатывающей функции/Адама:

1. Если куча яблок это куча яблок, то возьми яблоко из кучи.
2. Если то что ты взял — это яблоко, то мой его и клади в корзину.
3. Если то что ты взял — коробка, то открой коробку. Если в коробке яблоко иди к шагу 2.
4. Если же в коробке другая коробка, то иди к шагу 3.
5. Когда от кучи яблок не осталось и следа отдай нам корзину.
6. Если куча яблок совсем не куча яблок, то отдай это, чем бы они ни было.

Рекурсивная функция с reduce( ) будет выглядеть так:

function flatten(arr) {
  if (Array.isArray(arr)) {
  return arr.reduce(function(done,curr){
    return done.concat(flatten(curr));
    }, []);
  } else {
    return arr;
  }
}

// [ 1, 2, 3, 4 ]

Терпение и я всё объясню.

Рекурсия

Действия функции сопровождающееся вызовом самой себя. Рекурсия используется для решения проблем, которые содержат более мелкие проблемы. Рекурсивная функция, как правило, принимает два атрибуита: базовый регистр (конец рекурсии) или рекурсивный регистр (продолжается рекурсия). (MDN)

Если вы посмотрите на наш код выше, вы увидите, что flatten () появляется дважды. В первый раз, когда он появляется, он говорит Адаму, что делать с кучей яблок. Во второй раз он рассказывает ему, что делать с тем, что он сейчас держит, давая указания в случае, если это яблоко и в случае, если это не яблоко. Следует отметить, что эти инструкции являются повторением первоначальных инструкций, с которых мы начали — и это рекурсия.

Для ясности разберём всё строчка за строчкой:

1. function flatten(arr) { — мы называем нашу общую функцию и указываем что она примет аргумент arr.
2. if (Array.isArray(arr)) { — мы проверяем является ли полученное массивом.
3. return arr.reduce(function(done,curr){ — если предыдущая строка возвращает true и аргумент является массивом вы передаём его в reduce ( ) — это наш рекурсивный регистр.
4. return done.concat(flatten(curr)); — неожиданный поворот сюжета! Функция, которую мы вызываем — это та самая функция в которой мы находимся сейчас. Вкратце: начинайте заново с самого верха.
5. }, []); — мы говорим нашей функции reduce начинать с пустого аккумулятора (done) и помещать то, что вернёт функция именно в него.
6. } else { — это разрешает те случаи когда строка 2 возвращает false, то есть когда аргумент не является массивом.
7. return arr; — вернуть то, чему бы arr не было бы равно (предположительно чистому яблоку). Это уже на базовый регистр, который выводит нас из рекурсии.
8. } — завершение блока else.
9. } — завершение общей функции.

И мы закончили! Мы перешли от 24-строкового, 4-слойного-вложенного цикла for к более сжатому и лаконичному 9-строчному рекурсивному решению. Reduce и рекурсия могут поначалу показаться сложными для понимания, но это ценные инструменты которые в будущем сэкономят вам множество усилий как только вы их поймёте.

И не беспокойтесь об Адаме, нашем неработающем разработчике. Он получил так много внимания после этой статьи, что он открыл свою собственную фабрику яблочных пирогов, управляемую AI. Он очень доволен.

+1 вам, если ожидали шутку про Адамово Яблоко.

---

Данная статья рискует констатировать очевидные вещи. Но следует задать вопрос: «Очевидные для кого?».

Впервые делаю перевод статьи, от того буду благодарен за любые правки, исправения и указание на недочёты.

• Оригинал статьи. Vicky Lai's Blog
• MDN