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

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

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

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 ( ) как о чём-то вне работы разработчика. Знакомьтесь, это Адам. Основная функция Адама состоит в том, чтобы взять яблоки из кучи, помыть их, а затем поместить одно за другим в корзину. Эта корзина блестящих яблок предназначена для того, чтобы стать вкусными яблочными пирогами. Это очень важная работа.
image
Яблоки + Человеческие усилия = Пирог. Не путайте формулу с рецептом яблоко-человеческого пирога, он не столь вкусный.

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

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


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

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

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

  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. Он очень доволен.
image
+1 вам, если ожидали шутку про Адамово Яблоко.



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

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

Поделиться публикацией
Похожие публикации
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 11
  • +4
    С одной стороны, очень хочется оставить едкий комментарий типа «когда будет статья про понимание Array.length?». С другой, я действительно нередко наблюдал, как начинающие погромисты тупят при знакомстве с reduce. В следующий раз попробую подвергнуть такого человека чтению этой статьи.
    • +2

      Ваш пример — отличный пример подмены понятий. Никаких сложностей переписать for на такую-же рекурсивную форму, как ваш reduce нет, и, соответственно, нет перечисленных проблем. Да еще и намеренно написан ужасный нечитаемый код. Нда.


      И опять же, в первом случае у вас не создается сотен промежуточных массивов, что потребление памяти, что время выполнения меньше, даже если переписать на рекурсию (передавая var flat = [] как параметр).

      • +2

        Я как-то против вашего решения.


        Если начал использовать функциональный подход, то становится трудно остановиться, а вы решились на reduce и тут же остановились на грязной функции


        flatten у вас делает слишком много работы — она и самим array занимается, и лезет в его вещи и там шурует и объявляет ещё функции внутри и создает кучу всего.


        Предлагаю такую функцию:


        var flattenReduceArray = (result, item) => Array.isArray(item) ? item.reduce(flattenReduceArray, result) : [...result, item]

        Читабельный ES5 вариант:


        function flattenReduceArrayES5 (result, item) {
          if (Array.isArray(item)) {
            return item.reduce(flattenReduceArrayES5, result)
          } else {
            result.push(item);
            return result;
          }
        }

        Во-первых, не создается никаких функций и промежуточных массивов — все пишется в один массив


        Во-вторых, функция занимается исключительно элементами массива и ничем больше.


        В-третьих — она быстрее. Я тут ради эксперимента попробовал использовать jsperf, если кто-то может посмотреть и сказать что я таки правильно посчитал — буду благодарен.


        Вот: https://jsperf.com/flatten1

        • +6
          Если мы знаем максимальное количество вложенных массивов, с которыми нам предстоит работать (в примере их 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]
          

          Слишком мало вложенности, хипстеры могут не клюнуть! Давайте вручную напишем цикл глубиной в 20! А еще лучше глубиной в 30 элементов!

          Блин, автор, неужели вы считаете своих читателей такими идиотами, что скармливаете им такую ересь? Это уже просто оскорбительно!

          пс. да, это перевод.
          • 0
            То есть те двое, кто меня минусанули считают, что в императивном стиле пишут именно так? Серьезно?
            • +3
              Я думаю иперативно можно написать так:
              let arr = [1, [2], [3, [[4]]]];
              
              while (arr.some(Array.isArray)) {
              	arr = [].concat(...arr);
              }
              
              console.log(arr);
              
              • 0
                Дорогой дневник! Сегодня я узнал, что Array#concat принимает больше одного аргумента. Это знание изменит мою жизнь. Или нет, но всё равно прикольно.
                • 0

                  В вашем подходе будет много лишних проходов по массиву в arr.some(Array.isArray). В рекурсивном варианте такого не случится

                  • 0
                    Быстрее, чем вариант из статьи (в Chrome и Edge), рекурсия — это тоже не бесплатно:
                    https://jsperf.com/flatten2

                    Но в Firefox — худший. И в целом не лучший, особенно в сравнении с flattenReduceArrayES5 от Fen1kz

                    Но, согласитесь, ни одной новой переменной, даже функции нет, простой однострочник, TheShock правильно подметил, что автор нас пытается ввести в заблуждение.
              • +1
                C римскими цифрами вместо i: XVIII, XIX, XX… Я всегда думал, что лучше писать как в математике, i, j, k и т.д., а тут вот какой пример страшный.
              • 0
                А можно использовать js «магию»:
                const arr = [1, [2], [3, [[4]]]]
                const result = arr.toString().split(',').map(el => parseInt(el));
                console.log(result);
                // [1, 2, 3, 4]
                

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.