В функциональном программировании свертывание ( также называемое сокращением , накоплением , агрегированием , сжатием или внедрением ) относится к семейству функций высшего порядка , которые анализируют рекурсивную структуру данных и посредством использования данной операции объединения рекомбинируют результаты рекурсивной обработки ее. составные части, создавая возвращаемую стоимость. Обычно свертка представлена объединяющей функцией , верхним узлом структуры данных и, возможно, некоторыми значениями по умолчанию, которые будут использоваться при определенных условиях. Затем сгиб приступает к объединению элементов иерархии структуры данных , систематически используя функцию.
Складки в некотором смысле двойственны развертываниям , которые принимают начальное значение и коркурсивно применяют функцию , чтобы решить, как постепенно построить корекурсивную структуру данных, тогда как сгиб рекурсивно разбивает эту структуру, заменяя ее результатами применения функции объединения в каждый узел по его конечным значениям и рекурсивным результатам ( катаморфизм или анаморфизм развертываний).
Складки можно рассматривать как последовательную замену структурных компонентов структуры данных функциями и значениями. Списки , например, во многих функциональных языках строятся из двух примитивов: любой список представляет собой либо пустой список, обычно называемый nil ( []), либо создается путем добавления префикса элемента перед другим списком, создавая так называемый узел cons . ( ), возникающий в результате применения функции (записанной в Haskell как двоеточие ). Складку в списках можно рассматривать как замену нуля в конце списка определенным значением и замену каждого минуса определенной функцией. Эти замены можно рассматривать в виде диаграммы: Cons(X1,Cons(X2,Cons(...(Cons(Xn,nil)))))cons(:)
Есть еще один способ последовательно выполнить структурное преобразование, при этом порядок двух звеньев каждого узла меняется при передаче в функцию объединения:
Эти изображения визуально иллюстрируют правый и левый сгиб списка. Они также подчеркивают тот факт, что foldr (:) []это функция идентификации в списках ( неглубокая копия на языке Лиспа ), поскольку замена cons на consи nil на nilне изменит результат. Диаграмма сгиба слева предлагает простой способ перевернуть список foldl (flip (:)) []. Обратите внимание, что параметры cons необходимо поменять местами, поскольку добавляемый элемент теперь является правым параметром объединяющей функции. Другой простой результат, который можно увидеть с этой точки зрения, — это написать функцию отображения высшего порядка в терминах foldr, составив функцию, воздействующую на элементы с cons, как:
карта f = foldr (( : ) . f ) [] где точка (.) — оператор, обозначающий композицию функции .
Такой взгляд на вещи обеспечивает простой путь к разработке складчатых функций для других алгебраических типов и структур данных, таких как различные виды деревьев. Пишется функция, которая рекурсивно заменяет конструкторы типа данных предоставленными функциями и любые константные значения типа предоставленными значениями. Такую функцию обычно называют катаморфизмом .
Свертывание списка [1,2,3,4,5]с помощью оператора сложения приведет к получению 15 — суммы элементов списка [1,2,3,4,5]. В грубом приближении эту складку можно представить как замену запятых в списке операцией +, что дает 1 + 2 + 3 + 4 + 5. [1]
В приведенном выше примере + — это ассоциативная операция , поэтому конечный результат будет одинаковым независимо от заключения в круглые скобки, хотя конкретный способ его вычисления будет другим. В общем случае неассоциативных бинарных функций порядок объединения элементов может влиять на конечное значение результата. В списках есть два очевидных способа сделать это: либо объединив первый элемент с результатом рекурсивного объединения остальных (так называемый сгиб вправо ) , либо объединив результат рекурсивного объединения всех элементов, кроме последнего, с последний элемент (называемый левой складкой ). Это соответствует тому, что бинарный оператор может быть либо правоассоциативным, либо левоассоциативным, в терминологии Haskell или Prolog . При правом сгибе сумма будет заключена в круглые скобки как 1 + (2 + (3 + (4 + 5))), тогда как при левом сгибе она будет заключена в круглые скобки как (((1 + 2) + 3) + 4) + 5.
На практике удобно и естественно иметь начальное значение, которое в случае правого сгиба используется при достижении конца списка, а в случае левого сгиба — то, что изначально объединяется с первым элементом списка. список. В приведенном выше примере значение 0 ( аддитивная идентичность ) будет выбрано в качестве начального значения, соответствующего 1 + (2 + (3 + (4 + (5 + 0))))правому сгибу и ((((0 + 1) + 2) + 3) + 4) + 5левому сгибу. Для умножения первоначальный выбор 0 не подойдет: 0 * 1 * 2 * 3 * 4 * 5 = 0. Единичным элементом умножения является 1. Это даст нам результат 1 * 1 * 2 * 3 * 4 * 5 = 120 = 5!.
Использование начального значения необходимо, когда объединяющая функция f асимметрична по своим типам (например, a → b → b), т.е. когда тип ее результата отличается от типа элементов списка. Затем необходимо использовать начальное значение того же типа, что и результат f , чтобы была возможна линейная цепочка приложений. Будет ли он ориентирован слева или справа, будет определяться типами, ожидаемыми от его аргументов объединяющей функцией. Если это второй аргумент, который должен быть того же типа, что и результат, то f можно рассматривать как бинарную операцию, которая связывается справа , и наоборот.
Когда функция является магмой , то есть симметрична по своим типам ( a → a → a), а тип результата такой же, как тип элементов списка, круглые скобки можно размещать произвольным образом, создавая таким образом двоичное дерево вложенных подвыражений, например: ((1 + 2) + (3 + 4)) + 5. Если бинарная операция f является ассоциативной, это значение будет четко определено, т. е. одинаково для любой скобки, хотя операционные детали того, как оно вычисляется, будут разными. Это может оказать существенное влияние на эффективность, если f не является строгим .
В то время как линейные складки ориентированы на узлы и действуют согласованно для каждого узла списка , древовидные складки ориентированы на весь список и действуют согласованно для групп узлов.
Часто хочется выбрать единичный элемент операции f в качестве начального значения z . Когда никакое начальное значение не кажется подходящим, например, когда кто-то хочет свернуть функцию, которая вычисляет максимум из двух своих параметров в непустом списке, чтобы получить максимальный элемент списка, существуют варианты и foldrкоторые foldlиспользуют последний и первый элемент списка соответственно в качестве начального значения. В Haskell и некоторых других языках они называются foldr1и foldl1, цифра 1 указывает на автоматическое предоставление начального элемента и на тот факт, что списки, к которым они применяются, должны иметь хотя бы один элемент.
Эти складки используют симметричную по типу бинарную операцию: типы ее аргументов и результата должны быть одинаковыми. Ричард Берд в своей книге 2010 года предлагает [2] «общую функцию свертывания для непустых списков» foldrn, которая преобразует свой последний элемент, применяя к нему дополнительную функцию аргумента, в значение типа результата перед началом самой складки, и таким образом, можно использовать асимметричную по типу двоичную операцию, такую как обычная, foldrдля получения результата типа, отличного от типа элемента списка.
Используя Haskell в качестве примера, foldlего foldrможно сформулировать в нескольких уравнениях.
foldl :: ( b -> a - > b ) - > b -> [ a ] -> bfoldl f z [] = zfoldl f z ( x : xs ) = foldl f ( f z x ) xs Если список пуст, результатом является начальное значение. Если нет, сверните хвост списка, используя в качестве нового начального значения результат применения f к старому начальному значению и первому элементу.
foldr :: ( a -> b - > b ) - > b -> [ a ] -> bfoldr f z [] = zfoldr f z ( x : xs ) = f x ( foldr f z xs ) Если список пуст, результатом является начальное значение z. Если нет, примените f к первому элементу и результату сгиба остальных.
Списки можно сворачивать в виде дерева, как для конечных, так и для неопределенно определенных списков:
foldt f z [ ] = zfoldtfz [ x ] = fxzfoldtfzxs = foldtfz ( пары fxs ) foldifz [ ] = zfoldifz ( x : xs ) = fx ( foldi _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ж z ( пары ж xs ) ) пары ж ( x : y : t ) = f x y : пары f t пары _ t = t В случае foldiфункции, чтобы избежать неконтролируемого вычисления в неопределенно определенных списках, функция не fдолжна всегда запрашивать значение своего второго аргумента, по крайней мере, не все или не сразу (см. пример ниже).
foldl1 f [ x ] = xfoldl1 f ( x : y : xs ) = foldl1 f ( f x y : xs ) _ foldr1 f [ x ] = xfoldr1 f ( x : xs ) = f x ( foldr1 f xs ) _ foldt1 f [ x ] = xfoldt1 f ( x : y : xs ) = foldt1 f ( f x y : пары f xs ) foldi1 f [ x ] = xfoldi1 f ( x : xs ) = f x ( foldi1 f ( пары _ _ хз ) ) При наличии ленивой или нестрогой оценки foldrнемедленно вернет применение f к началу списка и рекурсивный случай свертывания по остальной части списка. Таким образом, если f может выдать некоторую часть своего результата без ссылки на рекурсивный случай «справа», т. е. во втором аргументе , а остальная часть результата никогда не требуется, то рекурсия остановится (например, ) . Это позволяет сгибам вправо работать с бесконечными списками. Напротив, он сразу же вызовет себя с новыми параметрами, пока не достигнет конца списка. Эту хвостовую рекурсию можно эффективно скомпилировать как цикл, но она вообще не может работать с бесконечными списками — она будет бесконечно рекурсивно выполняться в бесконечном цикле .head == foldr (\a b->a) (error "empty list")foldl
Достигнув конца списка, выражение фактически строится из foldlвложенных приложений с углублением влево f, которое затем представляется вызывающей стороне для оценки. Если бы здесь функция fсначала обратилась к своему второму аргументу и смогла бы выдать некоторую часть своего результата без ссылки на рекурсивный случай (здесь, слева от нее , т. е. в ее первом аргументе), тогда рекурсия остановилась бы. Это означает, что хотя foldrрекурсия выполняется справа , она позволяет функции ленивого объединения проверять элементы списка слева; и наоборот, хотя foldlрекурсия выполняется слева , она позволяет функции ленивого объединения проверять элементы списка справа, если она того пожелает (например, ).last == foldl (\a b->b) (error "empty list")
Обращение списка также является хвостовой рекурсией (это можно реализовать с помощью ). В конечных списках это означает, что свертка влево и обратное могут быть составлены для выполнения складки вправо хвостовым рекурсивным способом (см. ), с модификацией функции так, чтобы она меняла порядок своих аргументов (т. е. ), хвостовая рекурсия строит представление выражения, которое могло бы построить правая складка. Постороннюю промежуточную структуру списка можно устранить с помощью техники стиля передачи продолжения ; аналогично ( требуется только в таких языках, как Haskell с его перевернутым порядком аргументов для функции объединения непохожих, например, в Scheme, где один и тот же порядок аргументов используется для объединения функций с обоими и ).rev = foldl (\ys x -> x : ys) []1+>(2+>(3+>0)) == ((0<+3)<+2)<+1ffoldr f z == foldl (flip f) z . foldl (flip (:)) []foldr f z xs == foldl (\k x-> k . f x) id xs zfoldl f z xs == foldr (\x k-> k . flip f x) id xs zflipfoldlfoldlfoldr
Другой технический момент заключается в том, что в случае левых сгибов с использованием ленивой оценки новый начальный параметр не оценивается до выполнения рекурсивного вызова. Это может привести к переполнению стека, когда кто-то достигает конца списка и пытается вычислить полученное потенциально гигантское выражение. По этой причине такие языки часто предоставляют более строгий вариант свертывания влево, который требует оценки начального параметра перед выполнением рекурсивного вызова. В Haskell это foldl'(обратите внимание на апостроф, произносится как «простое») в Data.Listбиблиотеке (однако необходимо помнить о том факте, что принудительное создание значения, созданного с помощью ленивого конструктора данных, само по себе не приведет к автоматическому принудительному использованию его составляющих). В сочетании с хвостовой рекурсией такие складки приближаются к эффективности циклов, обеспечивая работу с постоянным пространством, когда ленивая оценка конечного результата невозможна или нежелательна.
Используя интерпретатор Haskell , структурные преобразования, которые выполняют функции свертки, можно проиллюстрировать путем построения строки:
λ > foldr ( \ x y -> concat [ "(" , x , "+" , y , ")" ]) "0" ( показать карту [ 1 .. 13 ]) "(1+(2+(3) +(4+(5+(6+(7+(8+(9+(10+(11+(12+(13+0))))))))))))" λ > foldl ( \ x y -> concat [ "(" , x , "+" , y , ")" ]) "0" ( показать карту [ 1 .. 13 ]) "((((((((((( (0+1)+2)+3)+4)+5)+6)+7)+8)+9)+10)+11)+12)+13)" λ > foldt ( \ x y - > concat [ "(" , x , "+" , y , ")" ]) "0" ( показать карту [ 1 .. 13 ]) "(((((1+2)+(3+4)) +((5+6)+(7+8)))+(((9+10)+(11+12))+13))+0)" λ > foldi ( \ x y -> concat [ " (" , x , "+" , y , ")" ]) "0" ( показать карту [ 1 .. 13 ]) "(1+((2+3)+(((4+5)+(6 +7))+((((8+9)+(10+11))+(12+13))+0))))" Бесконечное древовидное сворачивание демонстрируется, например, при рекурсивном производстве простых чисел неограниченным решетом Эратосфена в Haskell :
простые числа = 2 : _Y (( 3 : ) минус [ 5 , 7 .. ] .foldi ( \ ( x : xs ) ys -> x : объединение xs ys ) [ ] .map ( \ p - > [ p * p , п * р + 2 * п .. ])) _Y г знак равно г ( _Y г ) -- = г . г . г . г . ... где функция unionлокально работает с упорядоченными списками, чтобы эффективно создавать объединение их множествminus и разницу множеств .
Конечный префикс простых чисел кратко определяется как операция свертывания разности множеств над списками нумерованных кратных целых чисел, как
primesTo n = foldl1 минус [[ 2 * x , 3 * x .. n ] | х <- [ 1 .. п ]] Для конечных списков, например, сортировку слиянием (и ее разновидность, удаляющую дубликаты nubsort) можно легко определить с помощью древовидного свертывания как
сортировка слиянием xs = слияние [ ] [[ x ] | x <- xs ] nubsort xs = фолд- объединение [] [[ x ] | х <- хз ] с функцией merge, сохраняющей дубликаты, вариант union.
Функции headи lastмогли быть определены путем свертывания как
head = foldr ( \ xr - > x ) ( ошибка « head : Пустой список » ) _ _ _ _ _ _ _ _ _ Fold — полиморфная функция. Для любого g , имеющего определение
г [] знак равно v г ( Икс : Икс ) знак равно ж Икс ( г Икс ) тогда g можно выразить как [14]
g = Foldr f v Кроме того, в ленивом языке с бесконечными списками комбинатор с фиксированной точкой может быть реализован через свертку, [15] доказывая, что итерации можно свести к сверткам:
y f = foldr ( \ _ -> f ) не определено ( повторение не определено ) functools.reduce: import functoolsreduce:from functools import reduce