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

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

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

См. также[править]

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