В функциональном программировании fold ( также называемый reduce , accumpl , gregate , compress или inject ) относится к семейству функций высшего порядка , которые анализируют рекурсивную структуру данных и посредством использования заданной операции комбинирования рекомбинируют результаты рекурсивной обработки ее составных частей, создавая возвращаемое значение. Обычно fold представлен функцией комбинирования , верхним узлом структуры данных и, возможно, некоторыми значениями по умолчанию, которые будут использоваться при определенных условиях. Затем fold переходит к объединению элементов иерархии структуры данных , используя функцию систематическим образом.
Свертки в некотором смысле двойственны разверткам , которые берут начальное значение и применяют функцию корекурсивно, чтобы решить, как постепенно построить корекурсивную структуру данных, тогда как свертка рекурсивно разбивает эту структуру, заменяя ее результатами применения объединяющей функции в каждом узле к ее конечным значениям и рекурсивным результатам ( катаморфизм , в отличие от анаморфизма разверток).
Складки можно рассматривать как последовательную замену структурных компонентов структуры данных функциями и значениями. Списки , например, строятся во многих функциональных языках из двух примитивов: любой список является либо пустым списком, обычно называемым nil ( []), либо создается путем добавления префикса элемента перед другим списком, создавая то, что называется узлом cons ( ), полученным в результате применения функции (записывается как двоеточие в Haskell ). Можно рассматривать складку в списках как замену nil в конце списка определенным значением и замену каждого cons определенной функцией. Эти замены можно рассматривать в виде диаграммы : Cons(X1,Cons(X2,Cons(...(Cons(Xn,nil)))))cons(:)
Есть еще один способ выполнить структурное преобразование последовательным образом, при этом порядок двух связей каждого узла меняется на противоположный при подаче в функцию объединения:
Эти рисунки наглядно иллюстрируют правую и левую складки списка. Они также подчеркивают тот факт, что foldr (:) []является функцией идентичности списков ( поверхностная копия на языке Lisp ), поскольку замена cons на consи nil на nilне изменит результат. Диаграмма левой складки предлагает простой способ перевернуть список, foldl (flip (:)) []. Обратите внимание, что параметры cons должны быть перевернуты, поскольку элемент для добавления теперь является правым параметром функции объединения. Другой простой результат, который можно увидеть с этой точки зрения, — это запись функции отображения более высокого порядка в терминах foldr, путем составления функции для воздействия на элементы с cons, как:
карта f = foldr (( : ) . f ) [] где точка (.) — оператор, обозначающий композицию функций .
Такой взгляд на вещи обеспечивает простой путь к проектированию функций типа fold-like для других алгебраических типов данных и структур, таких как различные виды деревьев. Пишется функция, которая рекурсивно заменяет конструкторы типа данных предоставленными функциями, а любые константные значения типа — предоставленными значениями. Такая функция обычно называется катаморфизмом .
Свертывание списка [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сформулировать это с помощью нескольких уравнений.
сложить :: ( b -> a -> b ) -> b -> [ a ] -> b сложить f z [] = z сложить f z ( x : xs ) = сложить f ( f z x ) xs Если список пуст, результатом будет начальное значение. Если нет, сверните хвост списка, используя в качестве нового начального значения результат применения f к старому начальному значению и первому элементу.
складка :: ( a -> b -> b ) -> b -> [ a ] -> b складка f z [] = z складка f z ( x : xs ) = f x ( складка f z xs ) Если список пуст, результатом будет начальное значение z. Если нет, то применим f к первому элементу и результату свертывания остальных.
Списки можно сворачивать в древовидной форме, как для конечных, так и для неопределенно определенных списков:
сложить f z [] = z сложить f z [ x ] = f x z сложить f z xs = сложить f z ( пары f xs ) сложить i f z [] = z сложить i f z ( x : xs ) = f x ( сложить i f z ( пары f xs )) пары f ( x : y : t ) = f x y : пары f t пары _ t = t В случае foldiфункции, чтобы избежать ее неконтролируемого вычисления в неопределенно определенных списках, функция не fдолжна всегда требовать значение своего второго аргумента, по крайней мере, не все его или не немедленно (см. пример ниже).
сложитьl1 f [ x ] = x сложитьl1 f ( x : y : xs ) = сложитьl1 f ( f x y : xs ) складка1 f [ x ] = x складка1 f ( x : xs ) = f x ( складка1 f xs ) сложитьt1 f [ x ] = x сложитьt1 f ( x : y : xs ) = сложитьt1 f ( f x y : пары f xs ) сложитьi1 f [ x ] = x сложитьi1 f ( x : xs ) = f x ( сложитьi1 f ( пары f xs )) При наличии ленивой или нестрогой оценки 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")
Обращение списка также является хвостовой рекурсией (ее можно реализовать с помощью ). В конечных списках это означает, что left-fold и reverse могут быть скомпонованы для выполнения right fold хвостовым рекурсивным способом (ср. ), с модификацией функции так, чтобы она обращала порядок своих аргументов (т. е. ), хвостовым рекурсивным построением представления выражения, которое построила бы right-fold. Постороннюю промежуточную структуру списка можно устранить с помощью техники стиля продолжения-передачи , ; аналогично, ( требуется только в таких языках, как 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 , структурные преобразования, выполняемые функциями свертки, можно проиллюстрировать путем построения строки:
λ > свёртка ( \ x y -> конкат [ "(" , x , "+" , y , ")" ]) "0" ( карта показать [ 1 .. 13 ]) "(1+(2+(3+(4+(5+(6+(7+(8+(9+(10+(11+(12+(13+0)))))))))))))))" λ > свёртка ( \ x y -> конкат [ "(" , x , "+" , y , ")" ]) "0" ( карта показать [ 1 .. 13 ]) "((((((((((((0+1)+2)+3)+4)+5)+6)+7)+8)+9)+10)+11)+12)+13)" λ > свёртка ( \ x y -> конкат [ "(" , x , "+" , y , ")" ]) "0" ( карта показать [ 1 .. 13 ]) "(((((1+2)+(3+4))+((5+6)+(7+8)))+(((9+10)+(11+12))+13))+0)" λ > сложить ( \ 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 .. ] . сложение ( \ ( x : xs ) ys -> x : объединение xs ys ) [] . отображение ( \ p -> [ p * p , p * p + 2 * p .. ])) _Y g = g ( _Y g ) -- = g . g . g . g . ... где функция unionработает с упорядоченными списками локально, чтобы эффективно производить их объединение множеств и minusих разность множеств .
Конечный префикс простых чисел кратко определяется как свертывание операции разности множеств над списками перечислимых кратных целых чисел, как
primesTo n = foldl1 минус [[ 2 * x , 3 * x .. n ] | x <- [ 1 .. n ]] Для конечных списков, например, сортировку слиянием (и ее разновидность с удалением дубликатов nubsort) можно легко определить с помощью древовидной свертки как
mergesort xs = foldt merge [] [[ x ] | x <- xs ] nubsort xs = foldt union [] [[ x ] | x <- xs ] с функцией, mergeсохраняющей дубликаты, вариантом union.
Функции headи lastмогли быть определены посредством свертывания как
head = foldr ( \ x r -> x ) ( ошибка "head: Пустой список" ) last = foldl ( \ a x -> x ) ( ошибка "last: Пустой список" ) Складка — полиморфная функция. Для любого g, имеющего определение
г [] = v г ( х : хs ) = f х ( г хs ) тогда g можно выразить как [12]
г = складка ф v Кроме того, в ленивом языке с бесконечными списками комбинатор с фиксированной точкой может быть реализован с помощью свёртки, [13] доказывая, что итерации можно свести к свёрткам:
y f = foldr ( \ _ -> f ) не определено ( повтор не определено ) functools.reduce: import functoolsreduce:from functools import reduce