- Свёртка списка
-
Свёртка списка (англ. folding, также известна как reduce, accumulate) в программировании — функция высшего порядка, которая производит преобразование структуры данных к единственному атомарному значению при помощи заданной функции. Операция свёртки часто используется в функциональном программировании при обработке списков.
Свёртка может быть обобщена на произвольный алгебраический тип данных при помощи понятия катаморфизма из теории категорий.
Содержание
Описание
Функция свёртки обычно принимает три аргумента: комбинирующую функцию
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) ... ))
Если бинарная операция является ассоциативной, то скобки можно расставлять произвольным образом, создавая "дерево" вложенных выражений, как например .
Реализация
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
вычисляется сумма элементов.См. также
Литература
- 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.
Категория:- Функциональное программирование
Wikimedia Foundation. 2010.