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

У этого термина существуют и другие значения, см. Свёртка.

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

Свёртка может быть обобщена на произвольный алгебраический тип данных при помощи понятия катаморфизма из теории категорий.

Описание

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

Пусть требуется найти сумму чисел списка (1 2 3 4 5), т.е. значение выражения $1 + 2 + 3 + 4 + 5$. Так как сложение является ассоциативным, порядок вычисления данного выражения не влияет на результат. Однако для произвольной бинарной комбинирующей функции порядок вычисления может иметь значение. Таким образом, для однозначного вычисления выражения требуется задать порядок вычислений.

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

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

На практике иногда бывает нужным задать не-нулевое начальное значение, которое будет использовано при первом применении комбинирующей функции. При нулевом начальном значении можно опустить вычисление выражения с его участием: $(((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) ... ))

Если бинарная операция является ассоциативной, то скобки можно расставлять произвольным образом, создавая "дерево" вложенных выражений, как например $(1+2)+((3+4)+5)$.

Реализация

Haskell

В Haskell левоассоциативная свёртка уже присутствует как стандартная функция foldl, а правоассоциативная — foldr. Но их можно определить и следующим образом:

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl _ z []     = z
foldl f z (x:xs) = foldl f (f z x) xs
 
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

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

Оба вышеуказанных вида свертки - линейны. Можно также определить свертку по типу дерева, как для конечных так и для бесконечных списков:

foldt :: (a -> a -> a) -> a -> [a] -> a
foldt f z []     = z
foldt f z [x]    = x
foldt f z xs     = foldt f z (pairs f xs)
 
foldi :: (a -> a -> a) -> a -> [a] -> a
foldi f z []     = z
foldi f z (x:xs) = f x (foldi f z (pairs f xs))
 
pairs :: (a -> a -> a) -> [a] -> [a]
pairs f (x:y:t)  = f x y : pairs f t
pairs f t        = t

Внимательное рассмотрение типов свертываемых функций выявляет их важное свойство: симметричность типов (a -> a -> a) (что и позволяет произвольную "расстановку скобок" в свертке деревом, как например ((x+y)+(z+w)) ), в отличие от линейных сверток где их типы несимметричны ((a -> b -> b) для правой и (b -> a -> b) для левой свертки). Конкретно это означает что для возможности свертки деревом тип элемента списка вместе с бинарной операцией f должен представлять собой моноид, а в линейном случае это не обязательно.

Для того чтобы свертка бесконечно-определенного списка (foldi) не зациклилась, свертываемая функция f должна быть лево-предпочитающей: не требовать значения своего "правого" т.е. второго аргумента при хотя-бы некоторых значениях своего "левого" т.е. первого аргумента, а если элементы списков сами являются списками то хотя-бы не требовать их значений сразу (для примера см. Haskell - простые числа где unionAll = foldi (\(x:xs) ys -> x : union xs ys) [] ).

Lisp и Scheme

(define (foldl f start seq)
  (if (null? seq)
      start
      (foldl f (f start (car seq)) (cdr seq))))

Ruby

# Функция для расчёта факториала числа с помощью свёртки списка
def fact(num)
  (2 .. num.to_i).reduce( 1 ) { |res, val| res * val}
end

Python

# Суммирование элементов списка с помощью свёртки
reduce( lambda x, y: x + y, list )

C#

// Поиск минимального элемента в списке с помощью свёртки списка
using System.Linq;
int min = Enumerable.Range(1,100).Min();

Perl

# Поиск минимального элемента в списке с помощью свёртки списка
use List::Util qw(reduce);
my $elems_sum = reduce { $a < $b ? $a : $b } (1..100);

Clojure

# Поиск максимального элемента в списке с помощью свёртки списка
(reduce max (range 1 10))
# Суммирование всех значений списка, без указания начального значения
(reduce +  (range 5))

Примеры

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

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

Здесь:

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

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

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

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

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

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

Пример программы на языке Scala, которая суммирует все элементы списка который передаётся через аргументы.

 object Main {
   def main(args: Array[String]) {
     val elems = args map Integer.parseInt
     println("Сумма аргументов: " + elems.foldRight(0) (_ + _))
   }
 }

С помощью метода map перебираются все аргументы. Все они преобразовываются в целое число методом Integer.parseInt и добавляются в список (массив) elems. Затем с помощью метода свёртки списка foldRight вычисляется сумма элементов.

См. также

Имеется викиучебник по теме
«Свёртка списка»

Map

Литература

• 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. — Т. 9. — № 4. — С. 355–372. — ISSN 0956-7968.