Складка (функция высшего порядка)
Семейство функций высшего порядка

В функциональном программировании 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: Пустой список" )

На разных языках

ЯзыкЛевая складкаПравая складкаЛевая складка без начального значенияПравая складка без начального значенияРаскрытьПримечания
АПЛfunc⍨/⌽initval,vectorfunc/vector,initvalfunc⍨/⌽vectorfunc/vector
С# 3.0ienum.Aggregate(initval, func)ienum.Reverse().Aggregate(initval, func)ienum.Aggregate(func)ienum.Reverse().Aggregate(func)Aggregateявляется методом расширения
ienum является IEnumerable<T>
Аналогично во всех языках .NET
С++std::accumulate(begin, end, initval, func)std::accumulate(rbegin, rend, initval, func)в заголовке <numeric>
begin, end, rbegin, rendитераторы
funcмогут быть указателем функции или объектом функции
С++17(initval op ... op pack)(pack op ... op initval)(... op pack)(pack op ...)Выражение fold (только для вариативных шаблонов ): opэто бинарный оператор (оба ops должны быть одинаковыми, например, ), это нерасширенный пакет параметров.(std::cout << ... << args)pack
С++23std::ranges::fold_left(range, initval, func)std::ranges::fold_right(range, initval, func)std::ranges::fold_left_first(range, func)std::ranges::fold_right_last(range, func)Оба std::ranges::fold_left_firstи std::ranges::fold_right_lastвозвращаются, std::optionalучитывая пустоту range.
CFMLobj.reduce(func, initial)obj.reduce(func)Где funcполучает в качестве аргументов результат предыдущей операции (или initialзначение на первой итерации); текущий элемент; индекс или ключ текущего элемента; и ссылку наobj
Кложур(reduce func initval list)(reduce func initval (reverse list))(reduce func list)(reduce func (reverse list))См. также clojure.core.reducers/fold
Общий Лисп(reduce func list :initial-value initval)(reduce func list :from-end t :initial-value initval)(reduce func list)(reduce func list :from-end t)
Дreduce!func(initval, list)reduce!func(initval, list.reverse)reduce!func(list)reduce!func(list.reverse)в модулеstd.algorithm
ЭликсирList.foldl(list, acc, fun)List.foldr(list, acc, fun)Пример использования см. в документации.
ВязList.foldl(Fun, Accumulator, List)List.foldr(Fun, Accumulator, List)См. также API списка [1]
Эрлангlists:foldl(Fun, Accumulator, List)lists:foldr(Fun, Accumulator, List)
Фа#List.fold func initval list
Seq.fold func initval sequence		List.foldBack func list initvalList.reduce func list
Seq.reduce func sequence		List.reduceBack func listSeq.unfold func initval
Проблескlist.fold(list, initial, func)
iterator.fold(iterator, initial, func		list.fold_right(list, initial, func)list.reduce(list, func)
iterator.reduce(iterator, func)		iterator.unfold(initial, func)


ГосуIterable.fold(f(agg, e))
Iterable.reduce(init, f(agg, e))
Iterable.partition(f(e))		Все это методы расширения интерфейса Java Iterable, массивы также поддерживаются.
Крутоlist.inject(initval, func)list.reverse().inject(initval, func)list.inject(func)list.reverse().inject(func)
Хаскеллfoldl func initval listfoldr func initval listfoldl1 func listfoldr1 func listunfoldr func initvalДля foldlфункция сворачивания принимает аргументы в обратном порядке, чем для foldr.
ХаксеLambda.fold(iterable, func, initval)
Дж.verb~/|. initval,arrayverb/ array,initvalverb~/|. arrayverb/ arrayu/y применяет диаду u между элементами y. "J Dictionary: Вставить"
Ява 8+stream.reduce(initval, func)stream.reduce(func)
JavaScript 1.8
ECMAScript 5		array.reduce(func, initval)[3]array.reduceRight(func,initVal)array.reduce(func)array.reduceRight(func)Основными аргументами редуктора являются аккумулятор и текущее значение, а также мы можем использовать необязательные аргументы, такие как индекс и массив.array.reduceRight((acc,value, idx, array)=>{}, initvalue)
Джулияfoldl(op, itr; [init])foldr(op, itr; [init])foldl(op, itr)foldr(op, itr)
КотлинIterable.fold(initval, func)Iterable.foldRight(initval, func)Iterable.reduce(func)Iterable.reduceRight(func)Другие коллекции также поддерживают fold[4] и reduce. [5] Также существует Result.fold(onSuccess, onFailure), [6] который сводит a Result<T>(успех или неудача) к возвращаемому типу onSuccessи onFailure.
ЛФЭ(lists:foldl func accum list)(lists:foldr func accum list)
Логтокfold_left(Closure, Initial, List, Result)fold_right(Closure, Initial, List, Result)Мета-предикаты, предоставляемые объектом metaстандартной библиотеки. Сокращения foldlи foldrтакже могут использоваться.
Кленfoldl(func, initval, sequence)foldr(func, initval, sequence)foldl(func, sequence)foldr(func, sequence)
МатематикаFold[func, initval, list]Fold[func, initval, Reverse[list]]Fold[func, list]Fold[func, Reverse[list]]NestWhileList[func,, initval, predicate]Foldбез начального значения поддерживается в версиях 10.0 и выше.
МАТЛАБfold(@func, list, defaultVal)fold(@func, flip(list), defaultVal)fold(@func, list)fold(@func, flip(list))Требуется Symbolic Math Toolbox, поддерживаемый с версии R2016b.
Максимаlreduce(func, list, initval)rreduce(func, list, initval)lreduce(func, list)rreduce(func, list)
OCamlList.fold_left func initval list
Array.fold_left func initval array		List.fold_right func list initval
Array.fold_right func array initval
Оз{FoldL List Func InitVal}{FoldR List Func InitVal}
ПАРИ/ГПfold( f, A )
Перлreduce block initval, listreduce block listв List::Utilмодуле
PHParray_reduce(array, func, initval)array_reduce(array_reverse(array), func, initval)array_reduce(array, func)array_reduce(array_reverse(array), func)Если initvalне указано, используется NULL, поэтому это не настоящий foldl1. До PHP 5.3 initvalможет быть только целым числом. funcявляется обратным вызовом Архивировано 28.11.2020 на Wayback Machine . Попробуйте array_reduce онлайн.
Питон 2.xreduce(func, list, initval)reduce(lambda x, y: func(y, x), reversed(list), initval)reduce(func, list)reduce(lambda x, y: func(y, x), reversed(list))
Питон 3.xfunctools.reduce(func, list, initval)functools.reduce(lambda x, y: func(y, x), reversed(list), initval)functools.reduce(func, list)functools.reduce(lambda x, y: func(y, x), reversed(list))В модуле functools. [7]
РReduce(func, list, initval)Reduce(func, list, initval, right=TRUE)Reduce(func, list)Reduce(func, list, right=TRUE)R поддерживает правое свертывание, а также левое или правое свертывание с начальным значением или без него посредством аргументов rightи функции.initReduce
Ракетка(foldl func initval list)(foldr func initval list)
Рубинenum.inject(initval, &block)
enum.reduce(initval, &block)		enum.reverse_each.inject(initval, &block)
enum.reverse_each.reduce(initval, &block)		enum.inject(&block)
enum.reduce(&block)		enum.reverse_each.inject(&block)
enum.reverse_each.reduce(&block)		В Ruby 1.8.7+ также можно передать символ, представляющий функцию, вместо блока.
enum— это перечисление.
Обратите внимание, что эти реализации правых сверток неверны для некоммутативных типов &block(начальное значение также указано с неправильной стороны).
Ржавчинаiterator.fold(initval, func)iterator.rev().fold(initval, func)iterator.reduce(func)iterator.rev().reduce(func)iterator.rev()требуется iteratorбыть DoubleEndedIterator. [8]
Скалаlist.foldLeft(initval)(func)
(initval /: list)(func)		list.foldRight(initval)(func)
(list :\ initval)(func)		list.reduceLeft(func)list.reduceRight(func)Символический синтаксис свёртки Scala был задуман как напоминающий дерево с левым или правым наклоном, обычно используемое для объяснения операции свёртки, [9] но с тех пор был переосмыслен как иллюстрация падающего домино. [10] Двоеточие происходит из общего механизма синтаксиса Scala, посредством которого явный инфиксный оператор вызывается как метод для левого операнда с правым операндом, передаваемым в качестве аргумента, или наоборот, если последний символ оператора — двоеточие, здесь применяемое симметрично.

Scala также использует метод древовидных складок list.fold(z)(op). [11]

Схема Р 6 РС(fold-left func initval list)
(vector-fold func initval vector)		(fold-right func initval list)
(vector-fold-right func initval vector)		(reduce-left func defaultval list)(reduce-right func defaultval list)(unfold p f g seed [tail-gen])
unfold-right p f g seed [tail]
(vector-unfold f length initial-seed ···)
(vector-unfold-right f length initial-seed ···)		срфи/1 срфи/43
SmalltalkaCollection inject: aValue into: aBlockaCollection reduce: aBlockВ ANSI Smalltalk это определение не дано #reduce:, но во многих реализациях оно дано.
Стандартный МЛfoldl func initval list
Array.foldl func initval array		foldr func initval list
Array.foldr func initval array		Предоставленная функция принимает свои аргументы в кортеже. Для foldlфункция сворачивания принимает аргументы в том же порядке, что и для foldr.
Быстрыйarray.reduce(initval, func)
reduce(sequence, initval, func)		array.reverse().reduce(initval, func)
XPathfold-left($input, $zero, $action)
array:fold-left($input, $zero, $action)		fold-right($input, $zero, $action)
array:fold-right($input, $zero, $action)		Для каждого случая существуют две функции, поскольку XPath предлагает последовательности для неструктурированных и массивы для структурированных данных.
Xtenditerable.fold(initval,[func])iterable.reduce[func]

Универсальность

Складка — полиморфная функция. Для любого g, имеющего определение

 г [] = v г ( х : хs ) = f х ( г хs )

тогда g можно выразить как [12]

 г = складка ф v

Кроме того, в ленивом языке с бесконечными списками комбинатор с фиксированной точкой может быть реализован с помощью свёртки, [13] доказывая, что итерации можно свести к свёрткам:

 y f = foldr ( \ _ -> f ) не определено ( повтор не определено )

Смотрите также

Ссылки

  1. ^ "Haskell unit 6: The higher-order fold functions | Antoni Diller". www.cantab.net . Получено 2023-04-04 .
  2. ^ Ричард Берд, «Жемчужины функционального проектирования алгоритмов», Cambridge University Press 2010, ISBN 978-0-521-51338-8 , стр. 42 
  3. ^ "Array.prototype.reduce() - JavaScript | MDN". developer.mozilla.org . 2023-12-11 . Получено 2024-01-16 .
  4. ^ "fold - Kotlin Programming Language". Kotlin . Jetbrains . Получено 29 марта 2019 г. .
  5. ^ "reduce - язык программирования Kotlin". Kotlin . Jetbrains . Получено 29 марта 2019 г. .
  6. ^ "Результат - Язык программирования Kotlin". Kotlin . Jetbrains . Получено 29 марта 2019 .
  7. ^ Для справки functools.reduce: import functools
    Для справки reduce:from functools import reduce
  8. ^ "Итератор в core::iter". Rust . Rust Team . Получено 2021-06-22 .
  9. ^ Одерски, Мартин (2008-01-05). "Re: Блог: Мой вердикт по языку Scala". Группа новостей : comp.scala.lang. Архивировано из оригинала 14 мая 2015 года . Получено 14 октября 2013 года .
  10. ^ Стерлинг, Николас (28 июля 2010 г.). "Интуитивное ощущение оператора Scala /: (foldLeft)" . Получено 24 июня 2016 г.
  11. ^ "Fold API - Стандартная библиотека Scala". www.scala-lang.org . Получено 10.04.2018 .
  12. ^ Хаттон, Грэм (1999). "Учебник по универсальности и выразительности складки" (PDF) . Журнал функционального программирования . 9 (4): 355– 372. doi :10.1017/S0956796899003500 . Получено 26 марта 2009 г. .
  13. ^ Поуп, Берни. «Getting a Fix from the Right Fold» (PDF) . The Monad.Reader ( 6 ): 5–16 . Получено 1 мая 2011 г. .
  • «Функции высшего порядка — отображение, свертка и фильтрация»
  • «Раздел 6: Функции свертывания высшего порядка»
  • «Сложить в Tcl»
  • «Построение гомоморфизма списков из левых и правых складок»
  • "Волшебная складка"
Получено с "https://en.wikipedia.org/w/index.php?title=Fold_(higher-order_function)&oldid=1261356088"