Как реализовать карту, фильтровать и уменьшать с помощью рекурсии

kak realizovat kartu filtrovat i umenshat s pomoshhyu rekursii

Array.map

Мы все, вероятно, знаем Array.map. Он преобразует массив частей в согласовании с заданной функцией.

double = (x) => x * 2;
map(double, [1, 2, 3]);
// [2, 4, 6]

Я всегда видел, как это реализовано в таком направлении:

map = (fn, arr) => {
  const mappedArr = [];

  for (let i = 0; i < arr.length; i++) {
    let mapped = fn(arr[i]);

    mappedArr.push(mapped);
  }

  return mappedArr;
};

Это видео показало мне альтернативу Array.map исполнение. Это с JSConf 2014 года – задолго до того, как я перехватил функциональное программирование.

Редактировать: Дэвид Сизек и Стивен Блэкстоун любезно указали на крайние случаи и неоптимальную производительность по этому поводу. map исполнение. Я бы никому не советовал использовать это в реальном приложении. Мое намерение состоит в том, чтобы мы ценили этот рекурсивный подход, побуждающий к размышлению, и учился на этом. ?

Оригинальный пример в CoffeeScript, вот эквивалент JavaScript.

map = (fn, [head, ...tail]) =>
  head === undefined ? [] : [fn(head), ...map(fn, tail)];

Вместо этого можно использовать более безопасный вариант Дэвида Чизека.

map = (_fn_, [_head_, ..._tail_]) _=>_ (
  head === undefined && tail.length < 1
    ? []
    : [fn(head), ...map(fn, tail)]
);

Используя назначение деструктуризации ES6, мы сохраняем первый элемент массива в переменной head. Затем сохраняем все остальные элементы массива в tail.

Если head есть undefined, это означает, что у нас есть пустой массив, поэтому просто верните пустой массив. мы нанесен на карту Ничего.

map(double, []);
// []

Если head нет undefined мы возвращаем новый массив из fn(head) как первый элемент. Мы сейчас нанесен на карту первый элемент массива. Рядом с ним есть map(fn, tail) звонящий map снова, на этот раз с одним элементом меньше.

Так как map возвращает массив, мы используем синтаксис распространения ES6 для его конкатенации. [head].

Давайте пошагово рассмотрим это в отладчике. Вставьте это в консоль JavaScript вашего браузера.

map = (fn, [head, ...tail]) => {
  if (head === undefined) {
    return [];
  }

  debugger;

  return [fn(head), ...map(fn, tail)];
};

Теперь давайте map(double, [1, 2, 3]).

1*YB8D4_0XaIAGze7CKffX6A

Мы видим наши локальные переменные:

head: 1
tail: [2, 3]
fn: double

Мы знаем fn(head) есть 2. Это становится первым элементом нового массива. Тогда мы звоним map снова с fn и другие элементы массива: tail.

Итак перед начальным map звонок даже возвращается, мы будем звонить по телефону map пока массив не будет очищен. Как только массив станет пустым, head будет undefinedчто позволяет нашему базовому варианту запустить и завершить весь процесс.

1*dowa0N9An5o2V0quqD72nA

Во время следующего пробега, head есть 2 и tail есть [3].

Так как tail еще не пуст, нажмите следующую точку остановки для вызова map снова.

1*IMm0-zX10Zs5GGqu9Yl1ow

head есть 3и tail является пустым массивом. В следующий раз, когда эта функция будет запущена, она перейдет в строку 3 и, наконец, вернет отображенный массив.

И вот наш конечный результат:

1*m9PXMrrg9x9v013-Rl-UkQ

Массив.фильтр

Array.filter возвращает новый массив на основе элементов, удовлетворяющих заданной функции предиката.

isEven = (x) => x % 2 === 0;
filter(isEven, [1, 2, 3]);
// [2]

Рассмотрим это рекурсивное решение:

filter = (pred, [head, ...tail]) =>
  head === undefined
    ? []
    : pred(head)
    ? [head, ...filter(pred, tail)]
    : [...filter(pred, tail)];

Если map имеет смысл это будет легко.

Мы все еще фиксируем первый элемент массива в переменной под названием headа остальные в отдельном массиве, что называется tail.

И с тем же базовым случаем, если head есть undefinedверните пустой массив и закончите итерацию.

Но есть другое условное утверждение: только положить head в новом массиве if pred(head) есть trueпоскольку filter работает путём тестирования каждого элемента с предикативной функцией. Только тогда, когда возвращается сказуемое trueдобавляем этот элемент в новый массив.

Если pred(head) не возвращается trueпросто позвоните filter(pred, tail) без head.

Давайте быстро расширим и покроем это на консоли Chrome.

filter = (pred, [head, ...tail]) => {
  if (head === undefined) return [];

  if (pred(head)) {
    debugger;

    return [head, ...filter(pred, tail)];
  }

  debugger;

  return [...filter(pred, tail)];
};

И ищем числа ≤ 10:

filter(x => x <= 10, [1, 10, 20]);

1*hGkyWV3T_hDb1Hnav_lmAg

Поскольку наш массив [1, 10, 20], head является первым элементом, 1 и tail является массивом остальных: [10, 20].

Сказуемое проверяет если x ≤ 10, следовательно pred(1) возвращается true. Вот почему мы остановились на строке 4 debugger заявление.

Поскольку текущий head прошел тест, позволено входить в наш отфильтрованный массив. Но мы не кончили, поэтому мы звоним filter снова с тем же сказуемым и сейчас tail.

Перейдите к следующему debugger.

1*WESZIWb_dxhNNO-6-YJGuA

Мы позвонили filter с [10, 20] поэтому head сейчас 10, и tail есть [20]. Так как же tail уменьшаться с каждой последующей итерацией?

Мы на линии 4 debugger еще раз потому, что 10 ≤ 10. Перейти к следующей остановочной точке.

1*1U9o0ejjyzTvfjeEypYIFA

headсейчас 20 и tailпуст.

Поскольку 20 > 10, pred(head) возвращается false и наш отфильтрованный массив не будет включать его. Мы позвоним filter еще раз без head.

Однако в следующий раз filter выйдет под залог строки 2. Деструктурирование пустого массива дает вам undefined переменные. Продолжайте пройти эту точку остановки, чтобы получить возвращенное значение.

1*2BdKSxNZwaGJ9Sc1VAWjXA

Мне это кажется правильным!

Array.reduce

Последнее, но не менее важное, Array.reduce отлично подходит для возведения массива до одного значения.

Вот моя наивная reduce реализация:

reduce = (fn, acc, arr) => {
  for (let i = 0; i < arr.length; i++) {
    acc = fn(acc, arr[i]);
  }

  return acc;
};

И мы можем использовать это так:

add = (x, y) => x + y;
reduce(add, 0, [1, 2, 3]); // 6

Вы получите тот же результат с этой рекурсивной реализацией:

reduce = (fn, acc, [head, ...tail]) =>
  head === undefined ? acc : reduce(fn, fn(acc, head), tail);

Я считаю, что этот текст гораздо легче читать, чем рекурсивный map и filter.

Давайте пошагово рассмотрим это в консоли браузера. Вот расширенная версия с debugger заявления:

reduce = (fn, acc, [head, ...tail]) => {
  if (head === undefined) {
    debugger;

    return acc;
  }

  debugger;

  return reduce(fn, fn(acc, head), tail);
};

Тогда мы вызовем это в консоли:

add = (x, y) => x + y;
reduce(add, 0, [1, 2, 3]);

1*2oPtNloFlI-0OZ1B3IZENA

Раунд 1

Мы видим наши локальные переменные:

acc: наше первоначальное значение 0

fn: наш add функция

head: первый элемент массива, 1

tail: прочие элементы массива упакованы в a по отдельности массив, [2, 3]

Так как head не является undefined мы собираемся рекурсивно вызвать reduce, передавая свои необходимые параметры:

fn: Очевидно, что add снова функционировать?

acc: результат вызова fn(acc, head). Так как acc есть 0и head есть 1, add(0, 1) возвращается 1.

tail: остаточные элементы массива. Всегда используя хвост, мы продолжаем сокращать массив, пока ничего не останется!

Перейдите к следующему debugger.

Раунд 2

1*jYaNr_L9nJYw7N2uMMFsbQ

Локальные переменные:

acc: Теперь это 1потому что мы звонили reduce с fn(acc, head)какой был add(0, 1) в то время.

fn: Еще add!

head: Вспомните, как мы прошли предыдущую tail к reduce? Теперь это было деструктурировано, с head представляет его первый элемент, 2.

tail: Остался только один элемент, следовательно 3Упакован в массив сам по себе.

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

1*TVD3RgN7v4FW_j8mIogckQ

Ожидайте эти значения на следующей остановочной точке.

3 раунд

1*YjHE_30_rjv8s4__FNdy3g

Наши локальные переменные отвечают ожиданиям. headПервым и единственным элементом является 3.

И в нашем массиве остался только один элемент, tailпуст! Это означает, что следующая точка остановки будет нашей последней.

Давайте быстро оценим наши будущие локальные переменные:

1*agbXBbNDXSsqYRd6aYLD7w

Выделите конечную точку остановки.

4 раунд

1*E0CAeH84AfH9JBdtposIBA

Проверьте, на этот раз мы остановились на строке 3 вместо строки 6! head есть undefined поэтому мы возвращаем финал, 6! Он появится, если вы перейдете к следующей точке остановки.

1*VBzXT1FLhUP0_iRPJ_QTFQ1*ApR1Nzk791drSLLBzcq2Xw

Выглядит мне хорошо! Спасибо, что прочитали это.

Добавить комментарий

Ваш адрес email не будет опубликован.