Love Frontend
Сообщество
фронтенд разработчиков
EN

Рекурсия, правая свёртка и функциональное программирование

Дата публикации: 31.10.2019

В функциональном программировании свёртки fold или reduce — это функции высшего порядка, которые обрабатывают структуру данных и сворачивают их определенным образом в возвращаемое значение.

Например, в языке Haskell нет циклов, поэтому используется такой инструмент как рекурсия, т.е. вычисление функции с использованием вызова её самой.

Определим функцию isEmpty, которая присутствует во многих функциональных библиотеках, например в lodash. isEmpty понадобится в дальнейшем:

const isEmpty = array => array.length === 0

Откуда взялись функции для свёртки? Многие функции, принимающие массивы в качестве аргумента, могут быть выражены так:

function f(array) {
if (isEmpty(array)) {
return v // базовый случай
}
const [x, …xs] = array
return x # f(xs) // рекурсивный случай
}

Это # может быть как оператором, как показано выше, так и функцией двух аргументов, и выражена так # (x, f(xs)). Например:

function sum(array) {
if (isEmpty(array)) {
return 0
}
const [x, …xs] = array
return x + sum(xs)
// оператор + может быть и выражен через функцию:
// return add(x, sum(xs)),
// где const add = (x, y) => x + y
}

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

В нашем случае это момент когда массив пуст. Что же вернуть в таком случае? Идентичность (identity) для данной операции.

Ноль является идентичностью для операции сложения, поэтому сложение с нулем не изменит суммы чисел, так же как единица — это идентичность для операции умножения, false — идентичность для операции || (OR) и так далее.

2 + 0 = 1
5 * 1 = 5
true || false = true

*Проверьте себя. Что является идентичностью операции && (AND)?*

Функция высшего порядка, которая использует этот паттерн в функциональном языке Haskell называется foldr (сокращение foldRight). Напишем эту функцию в JavaScript:

function foldRight(f, v, array) {
if (isEmpty(array)) {
return v // базовый случай
}
const [x, …xs] = array
return f(x, foldRight(f, v, xs))
}

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

foldRight(f, v, [x0, x1, … xn]) = f(x0, f(x1, …, f(xn, v))

Рассмотрим на примере функции add. Сумма чисел в массиве посчитается как:

foldRight(add, 0, [1, 2, 3]) =
f(1, f(2, f(3, 0))) =
f(1, f(2, 3)) =
f(1, 5) =
6

Видно, что функция foldRight ассоциативна справа, что отражает её название.

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

const subFoldRight = (currentValue, accumulator) => accumulator - currentValue
foldRight(subFoldRight, 0, [1, 2, 3]) // -6

В то время как:

[1, 2, 3].reduceRight(subFoldRight, 0) // 2

У reduceRight другой порядок аргументов. Поэтому функцию нужно определить как:

const subReduceRight = (accumulator, currentValue) => accumulator - currentValue

Получится:

[1, 2, 3].reduceRight(subReduceRight, 0) // -6

Ещё одно отличие состоит в том, что современные движки JavaScript не оптимизируют рекурсию даже в т.н. «хвостовой позиции» и вызов функции foldRight на достаточно большом массиве может вызвать переполнение стека. Чтобы избежать этого, перепишем эту функцию в императивном стиле:

function foldRight(f, v, array) {
if (isEmpty(array)) {
return v
}
for (let i = array.length - 1; i >= 0; i -= 1) {
v = f (array[i], v)
}
return v
}

Прекрасно, теперь переполнения стека не случится.

В следующий раз рассмотрим как рекурсия работает применительно к левой свёртке. Оставайтесь с нами!

Оставьте свой e-mail чтобы получать уведомления о свежих статьях.