WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте

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

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

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

Для свёртки по ассоциативной операции порядок вычисления не влияет на результат, например, вычисление суммы чисел списка (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))(_ * _)

Литература

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии