Свёртка списка

Свёртка списка (англ. folding, также известна как reduce, accumulate) в программировании — функция высшего порядка, которая производит преобразование структуры данных к единственному атомарному значению при помощи заданной функции. Операция свёртки часто используется в функциональном программировании при обработке списков. Свёртка может быть обобщена на произвольный алгебраический тип данных при помощи понятия катаморфизма из теории категорий.

Функция свёртки обычно принимает три аргумента: комбинирующую функцию f, начальное значение start и структуру данных seq (список — в простейшем варианте). В зависимости от свойств комбинирующей функции могут быть различные реализации и различные стратегии вычисления. Иногда функция свёртки не принимает начального значения, но требует непустого списка; но во многих случаях бывает нужным задать ненулевое начальное значение, которое будет использовано при первом применении комбинирующей функции. Использование начального значения необходимо, когда тип результата комбинирующей функции отличается от типа элементов списка, тогда начальное значение должно быть того же типа что и тип результата.

Ассоциативность

Для свёртки по ассоциативной операции порядок вычисления не влияет на результат, например, вычисление суммы чисел списка (1 2 3 4 5), то есть его свёртки по сумме, может быть произведено в любом порядке: $1+(2+(3+(4+(5+0))))$ или $((((0+1)+2)+3)+4)+5$ или $0+(1+2)+((3+4)+5)$, что позволяет выполнять вычисление свёртки разных частей списка одновременно, то есть распараллеливать вычисление свёртки списка в многопроцессорных и кластерных системах.

Для неассоциативных операций порядок имеет значение, поэтому в общем случае для свёртки требуется задать порядок вычислений, в связи с этим различают свёртку справа (правоассоциативную) и свёртку слева (левоассоциативную). Например, для списка seq := (elem_1 elem_2 ... elem_n) функция левоассоциативной свёртки вычислит значение выражения:

(f ... (f (f start elem_1) elem_2) ... elem_n)

а правоассоциативная:

(f elem_1 (f elem_2 ... (f elem_n start) ... )).

Примеры

Факториал n можно представить как свёртку списка, состоящего из чисел от 2 до n, при помощи операции умножения (к примеру, на языке Haskell):

 fac n = foldl (*) 1 [2..n]

Здесь:

fac — объявление функции факториала

n — входной параметр

после знака = (равно) идёт определение функции

foldl — функция свёртки

1 — начальное значение для свёртки

[2..n] — задаётся список по которому следует делать свёртку — числа от 2 до n

Пример аналогичной функции на языке Scala:

 def fac(n: BigInt) = (BigInt(2) to n).foldLeft(BigInt(1))(_ * _)

Литература

• Bird, Richard. Pearls of Functional Algorithm Design (англ.). — Cambrigde: University Press, 2010. — 277 p. — ISBN 978-0-521-51338-8.
• Бёрд Р. Жемчужины проектирования алгоритмов: функциональный подход = Pearls of Functional Algorithm Design. — ДМК Пресс, 2013. — 330 с. — ISBN 978-5-94074-867-0. (недоступная ссылка)
• Hutton, Graham. A tutorial on the universality and expressiveness of fold (англ.) // Journal of Functional Programming. — Vol. 9, no. 4. — P. 355–372. — ISSN 0956-7968.