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

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

Свёртка бывает левоассоциативной (в языке Haskell — стандартная функция foldl) и правоассоциативной (foldr).

Определение функций

На языке Haskell левоассоциативная свёртка определяются следующим образом:

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

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

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

Соответственно, при помощи двух этих функций можно выразить любое рекурсивное вычисление на списках. Правоассоциативная функция foldr отвечает за произвольную рекурсию (катаморфизм для списков), левоассоциативная foldl — за хвостовую рекурсию.

Примеры

Функция суммирования всех элементов заданного списка:

sum :: (Num a) => [a] -> a
sum = foldl (+) 0

Функция для вычисления произведения всех элементов заданного списка:

product :: (Num a) => [a] -> a
product = foldl (*) 1

Функция для вычисления длины заданного списка:

length :: [a] -> Int
length = foldl (const . (1+)) 0

См. также

Два нижеприведённых ресурса наглядно показывают разницу между право- и левоассоциативной свёрткой.

• Левоассоциативная свёртка — пример сворачивания бесконечного списка единиц при помощи операции сложения.
• Правоассоциативная свёртка — пример сворачивания бесконечного списка единиц при помощи операции сложения.