Функциональные циклы в JavaScript | Кодементор

Одним из препятствий, которые я обнаружил, когда начал изучать языки функционального программирования, было отсутствие циклических конструкций. В то время мне было любопытно, как функциональные программисты заставляют работать даже самые простые программы без использования циклов. Я имею в виду, вам нужна какая-то форма цикла для печати чисел от 1 до 10, верно?

Неправильный!

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

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

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

Чтобы сделать решение как можно более переносимым, мы не будем использовать встроенные функции Array, такие как map, reduce и т. д. Потому что а) это будет жульничество, и б) идея в том, что вы можете взять код и перенести его на любой язык, который вам нравится, практически без усилий.

Начнем с итеративного подхода.

Итеративный подход в JavaScript

Наиболее часто используемый метод, и, вероятно, тот, который приходит на ум, когда вы читаете «суммировать все элементы в списке», — это итеративный подход. Это цикл по списку номеров и добавление их в аккумулятор, как только список будет исчерпан, возврат аккумулятора вызывающему абоненту.

function sum(numbers) {
  let acc = 0;
  for (let n of numbers) {
    acc += n;
  }
  return acc;
}

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

Функциональный подход в Erlang

Чтобы увидеть настоящий «функциональный цикл» в действии, мы портируем нашу маленькую программу на Erlang. Чистый функциональный язык программирования.

Если вы никогда раньше не видели программы на Erlang, синтаксис может показаться немного загадочным, но то, что делает программа, очень просто:

  • Разбивает список на структуру «голова/хвост».
  • Добавляет значение головы в аккумулятор.
  • Вызывает функцию «сумма», используя хвост и новое значение аккумулятора.

Эта операция продолжается до тех пор, пока список не будет исчерпан и аккумулятор не будет возвращен вызывающей стороне.

% Entry point.
sum(L) ->
  sum(L, 0).

% Recursive call.
sum([H|T], Acc) ->
  sum(T, H + Acc);
  
sum([], Acc) ->
  Acc.

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

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

Рекурсивный подход в JavaScript

Поскольку в JS у нас нет встроенного механизма для разбиения массива на [head|tail] структура, мы начнем с нее и создадим две вспомогательные функции, которые позволят нам это сделать.

Первая — это функция, которая возвращает то, что будет «головным узлом» связанного списка.

function head(list) {
  return len(list) > 0 ? list[0] : null;
}

Примечание. «len» — это пользовательская функция, которая выполняет проверку на нулевое значение и возвращает количество элементов в массиве. Вы можете увидеть код в сути, связанной с этим постом.

Вторая функция — еще один хелпер, который возвращает «хвост» списка. Это все элементы в списке, кроме первого. Если в списке меньше двух элементов, его конец считается нулевым.

function tail(list) {
  return len(list) > 1 ? list.splice(1) : null;
}

Хотите верьте, хотите нет, но имея только эти функции, у нас есть все необходимое для перебора последовательности элементов без циклов. Теперь давайте реализуем рекурсивную версию функции «сумма», чтобы увидеть эти помощники в действии.

// Entry point.
function sum(list) {
  return recSum(list, 0);
}

// Recursive call.
function recSum(list, acc) {
  let h = head(list);
  if (!h)
    return acc;
  return recSum(tail(list), h + acc);
}

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

Вывод

Помимо ваших личных предпочтений, в этом упражнении есть ключевой момент:

Каждый итерационный алгоритм может быть преобразован в рекурсивный.

Это не значит, что вы должны это делать, но знание этого может помочь вам при написании кода на собеседованиях или школьных заданиях, таких как: «Напишите программу для поиска среднего значения в последовательности бла, бла, бла… без использования петель! ».

Думаю, это все, что есть в этом коротком посте. Я надеюсь, что вы найдете это полезным.

Прежде чем вы пойдете, я планирую сделать короткую серию статей о рекурсии, чтобы охватить практические варианты использования, подводные камни, временную сложность, рекурсивные структуры данных, производительность, квадратичное поведение и так далее. Если вы увлекаетесь рекурсией, следите за обновлениями!

Спасибо за чтение!

Прежде чем ты уйдешь. Если вы только начинаете работать с алгоритмами и структурами данных, вам может быть интересна моя электронная книга « Структуры данных с нуля — версия JS (Это бесплатно для участников Kindle Unlimited.)


Структуры данных с нуля — JS Edition

Похожие записи

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

Ваш адрес email не будет опубликован. Обязательные поля помечены *