PROFILPELAJAR.COM

Свёртка списка (англ. 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.

PROFILPELAJAR.COM

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

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

Примеры

Литература

Read other articles:

Ga-Rei

Musée Saint-Remi

Bộ bộ kinh tâm (phim truyền hình)

Xarabank

Dušan Veselinović

Concours Eurovision de la chanson 2000

Lisa Sheridan

Пугачёва, Алла Борисовна

كأس السويد 2012–13

Penshurst

Relay race

2020年夏季奧林匹克運動會波蘭代表團

Кинематограф Аргентины

Монетный кризис в Германии XVII века

Advection

San Juan Bautista Tuxtepec

Dodge Series D5

Fraternité Notre-Dame

Edward Rowe Mores

St. Bartholomew's Anglican Church (Ottawa)