Сгиб (функция высшего порядка)
В функциональном программировании свертывание ( также называемое сокращением , накоплением , агрегированием , сжатием или внедрением ) относится к семейству функций высшего порядка , которые анализируют рекурсивную структуру данных и посредством использования данной операции объединения рекомбинируют результаты рекурсивной обработки ее. составные части, создавая возвращаемую стоимость. Обычно свертка представлена объединяющей функцией , верхним узлом структуры данных и, возможно, некоторыми значениями по умолчанию, которые будут использоваться при определенных условиях. структуры данных Затем сгиб приступает к объединению элементов иерархии , систематически используя функцию.
Складки в некотором смысле двойственны развертываниям , которые принимают начальное применяют функцию, значение и коркурсивно чтобы решить, как постепенно построить корекурсивную структуру данных, тогда как сгиб рекурсивно разбивает эту структуру, заменяя ее результатами применения объединяющей функции в точке каждый узел по его конечным значениям и рекурсивным результатам ( катаморфизм или анаморфизм развертываний).
По мере структурных преобразований
[ редактировать ] |
Складки можно рассматривать как последовательную замену структурных компонентов структуры данных функциями и значениями. Списки , например, во многих функциональных языках строятся из двух примитивов: любой список представляет собой либо пустой список, обычно называемый nil ( []), или создается путем добавления префикса элемента перед другим списком, создавая так называемый cons узел ( Cons(X1,Cons(X2,Cons(...(Cons(Xn,nil))))) ), возникающий в результате применения cons функция (записывается через двоеточие (:) в Хаскеле ). Складку в списках можно рассматривать как нуля в минуса конце списка определенным значением и замену каждого замену определенной функцией. Эти замены можно рассматривать в виде диаграммы:
Есть еще один способ последовательно выполнить структурное преобразование, при этом порядок двух звеньев каждого узла меняется при передаче в функцию объединения:
Эти изображения визуально иллюстрируют правый и левый сгиб списка . Они также подчеркивают тот факт, что foldr (:) [] — это функция идентификации в списках ( неглубокая копия на языке Лиспа ), заменяющая cons на cons и ноль с nil не изменит результат. Диаграмма сгиба слева предлагает простой способ перевернуть список: foldl (flip (:)) []. Обратите внимание, что параметры cons необходимо поменять местами, поскольку добавляемый элемент теперь является правым параметром объединяющей функции. Другой простой результат, который можно увидеть с этой точки зрения, — это записать функцию отображения высшего порядка в терминах foldr, составив функцию для воздействия на элементы с cons, как:
map 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] -> b
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
Если список пуст, результатом является начальное значение. Если нет, сверните хвост списка, используя в качестве нового начального значения результат применения f к старому начальному значению и первому элементу.
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
Если список пуст, результатом является начальное значение z. Если нет, примените f к первому элементу и результату сгиба остальных.
Древовидные складки
[ редактировать ]Списки можно сворачивать в виде дерева, как для конечных, так и для неопределенно определенных списков:
foldt f z [] = z
foldt f z [x] = f x z
foldt f z xs = foldt f z (pairs f xs)
foldi f z [] = z
foldi f z (x:xs) = f x (foldi f z (pairs f xs))
pairs f (x:y:t) = f x y : pairs f t
pairs _ t = t
В случае foldi функции, чтобы избежать ее неконтролируемого вычисления в неопределенно определенных списках, функция f должен не всегда требовать значение своего второго аргумента, по крайней мере, не полностью или не сразу (см. пример ниже).
Складки для непустых списков
[ редактировать ]foldl1 f [x] = x
foldl1 f (x:y:xs) = foldl1 f (f x y : xs)
foldr1 f [x] = x
foldr1 f (x:xs) = f x (foldr1 f xs)
foldt1 f [x] = x
foldt1 f (x:y:xs) = foldt1 f (f x y : pairs f xs)
foldi1 f [x] = x
foldi1 f (x:xs) = f x (foldi1 f (pairs 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")).
Обращение списка также является хвостовой рекурсией (его можно реализовать с помощью rev = foldl (\ys x -> x : ys) []). В конечных списках это означает, что свертку влево и обратную операцию можно составить так, чтобы свертка вправо выполнялась хвостовой рекурсией (см. 1+>(2+>(3+>0)) == ((0<+3)<+2)<+1), с модификацией функции f поэтому он меняет порядок своих аргументов (т. е. foldr f z == foldl (flip f) z . foldl (flip (:)) []), хвостовая рекурсия строит представление выражения, которое можно было бы построить сгибом вправо. Постороннюю промежуточную структуру списка можно устранить с помощью техники стиля передачи продолжения : foldr f z xs == foldl (\k x-> k . f x) id xs z; сходным образом, foldl f z xs == foldr (\x k-> k . flip f x) id xs z ( flip необходим только в таких языках, как Haskell с его перевернутым порядком аргументов для функции объединения foldl в отличие, например, от схемы, где для объединения функций используется один и тот же порядок аргументов. foldl и foldr).
Другой технический момент заключается в том, что в случае левых сгибов с использованием ленивой оценки новый начальный параметр не оценивается до выполнения рекурсивного вызова. Это может привести к переполнению стека, когда кто-то достигает конца списка и пытается вычислить полученное потенциально гигантское выражение. По этой причине такие языки часто предоставляют более строгий вариант свертывания влево, который требует оценки начального параметра перед выполнением рекурсивного вызова. В Хаскеле это foldl' (обратите внимание на апостроф, произносится как «простой») в Data.List библиотеку (однако необходимо помнить о том, что принудительное создание значения, созданного с помощью ленивого конструктора данных, само по себе не приведет к автоматическому принудительному использованию его составляющих). В сочетании с хвостовой рекурсией такие складки приближаются к эффективности циклов, обеспечивая работу с постоянным пространством, когда ленивая оценка конечного результата невозможна или нежелательна.
Примеры
[ редактировать ]Используя интерпретатор Haskell , структурные преобразования, которые выполняют функции свертки, можно проиллюстрировать путем построения строки:
λ> foldr (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
"(1+(2+(3+(4+(5+(6+(7+(8+(9+(10+(11+(12+(13+0)))))))))))))"
λ> foldl (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
"(((((((((((((0+1)+2)+3)+4)+5)+6)+7)+8)+9)+10)+11)+12)+13)"
λ> foldt (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
"(((((1+2)+(3+4))+((5+6)+(7+8)))+(((9+10)+(11+12))+13))+0)"
λ> foldi (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
"(1+((2+3)+(((4+5)+(6+7))+((((8+9)+(10+11))+(12+13))+0))))"
Бесконечное древовидное сворачивание демонстрируется, например, при рекурсивном производстве простых чисел неограниченным решетом Эратосфена в Haskell :
primes = 2 : _Y ((3 :) . minus [5,7..] . foldi (\(x:xs) ys -> x : union xs ys) []
. map (\p-> [p*p, p*p+2*p..]))
_Y g = g (_Y g) -- = g . g . g . g . ...
где функция union локально работает с упорядоченными списками, чтобы эффективно создавать их объединение множеств , и minus их установленная разница .
Конечный префикс простых чисел кратко определяется как операция свертывания разности множеств над списками нумерованных кратных целых чисел, как
primesTo n = foldl1 minus [[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) (error "head: Empty list")
last = foldl (\a x -> x) (error "last: Empty list")
На разных языках
[ редактировать ]| Язык | Левая складка | Правая складка | Левая складка без начального значения | Сгиб вправо без начального значения | Развернуть | Примечания |
|---|---|---|---|---|---|---|
| АПЛ | func⍨/⌽initval,vector
|
func/vector,initval
|
func⍨/⌽vector
|
func/vector
|
||
| С# 3.0 | ienum
|
ienum.Reverse()
|
ienum
|
ienum.Reverse()
|
Aggregate это метод расширения ienum это IEnumerable<T>Аналогично во всех языках .NET. | |
| С++ | std::accumulate(
|
std::accumulate(
|
в заголовке <numeric>begin, end, rbegin, rend являются итераторами func может быть указателем на функцию или объектом функции
| |||
| С++17 | (initval op ... op pack)
|
(pack op ... op initval)
|
(... op pack)
|
(pack op ...)
|
Выражение сгиба (только для шаблонов с переменным числом вариантов ): op является бинарным оператором (оба ops должны быть одинаковыми, например, (std::cout << ... << args)), pack представляет собой нерасширенный пакет параметров.
| |
| С++23 | std::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.
| |
| CFML | obj.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
|
reduce!func(list)
|
reduce!func(
|
в модуле 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 listSeq.fold func initval sequence
|
List.foldBack func list initval
|
List.reduce func listSeq.reduce func sequence
|
List.reduceBack func list
|
Seq.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
|
list.reverse()
|
list
|
list.reverse()
|
||
| Хаскелл | foldl func initval list
|
foldr func initval list
|
foldl1 func list
|
foldr1 func list
|
unfoldr func initval
|
Для foldl, функция свертывания принимает аргументы в порядке, противоположном тому, который используется для foldr.
|
| Смешанный | Lambda.fold(iterable, func, initval)
|
|||||
| Дж | verb~/|. initval,array
|
verb/ array,initval
|
verb~/|. array
|
verb/ array
|
u/y применяет диаду u между элементами y. «J-словарь: Вставка» | |
| Ява 8+ | stream.reduce
|
stream.reduce
|
||||
| JavaScript 1.8 ECMAScript 5 |
array.reduce[3]
|
array.reduce
|
||||
| Юлия | foldl(op, itr; [init])
|
foldr(op, itr; [init])
|
foldl(op, itr)
|
foldr(op, itr)
|
||
| Котлин | Iterable.fold
|
Iterable.foldRight
|
Iterable.reduce(func)
|
Iterable.reduceRight(func)
|
Другие коллекции также поддерживают fold[4] и reduce. [5] Существует также Result.fold(onSuccess, onFailure), [6] что уменьшает 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)
|
||
| OCaml | List.fold_left func initval listArray.fold_left func initval array
|
List.fold_right func list initvalArray.fold_right func array initval
|
||||
| Оз | {FoldL List Func InitVal}
|
{FoldR List Func InitVal}
|
||||
| СТАВКА/ГП | fold( f, A )
|
|||||
| Перл | reduce block initval, list
|
reduce block list
|
в List::Util модуль
| |||
| PHP | array_reduce(array, func, initval)
|
array_reduce(
|
array_reduce(array, func)
|
array_reduce(
|
Когда initval не указан, используется NULL, поэтому это не настоящий сгиб1. До версии PHP 5.3 initval может быть только целым числом. func — это обратный вызов. Архивировано 28 ноября 2020 г. на Wayback Machine . Попробуйте array_reduce онлайн.
| |
| Питон 2.x | reduce(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.x | functools.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))
|
В модуле funtools . [7] | |
| Р | Reduce(func, list, initval)
|
Reduce(func, list, initval, right=TRUE)
|
Reduce(func, list)
|
Reduce(func, list, right=TRUE)
|
R поддерживает свертывание вправо, а также свертывание влево или вправо с начальным значением или без него через right и init аргументы в пользу Reduce функция.
| |
| Ракетка | (foldl func initval list)
|
(foldr func initval list)
|
||||
| Руби | enumenum
|
enum.reverse_eachenum.reverse_each
|
enumenum.reduce(&block)
|
enum.reverse_eachenum.reverse_each
|
В 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 также реализованы древовидные складки с использованием метода | |
| Схема Р 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 |
| Смолток | aCollection inject: aValue into: aBlock
|
aCollection reduce: aBlock
|
ANSI Smalltalk не определяет #reduce: но многие реализации так делают.
| |||
| Стандартный ML | foldl func initval listArray.foldl func initval array
|
foldr func initval listArray.foldr func initval array
|
Предоставленная функция принимает свои аргументы в кортеже. Для foldl, функция свертывания принимает аргументы в том же порядке, что и для foldr.
| |||
| Быстрый | array.reduce(initval, func)reduce(sequence, initval, func)
|
array.reverse()
|
||||
| XPath | fold-left($input, $zero, $action)array:fold-left($input, $zero, $action)
|
fold-right($input, $zero, $action)array:fold-right($input, $zero, $action)
|
Для каждого случая существуют две функции, поскольку XPath предлагает последовательности для неструктурированных данных и массивы для структурированных данных. | |||
| Экстенд | iterable.fold(initval,[func])
|
iterable.reduce[func]
|
Универсальность
[ редактировать ]Fold — полиморфная функция. Для любого g, имеющего определение
g [] = v
g (x:xs) = f x (g xs)
тогда g можно выразить как [12]
g = foldr f v
Кроме того, в ленивом языке с бесконечными списками комбинатор с фиксированной запятой может быть реализован с помощью сгиба, [13] доказывая, что итерации можно свести к складкам:
y f = foldr (\_ -> f) undefined (repeat undefined)
См. также
[ редактировать ]- Агрегатная функция
- Итерированная бинарная операция
- Катаморфизм — обобщение складчатости.
- Гомоморфизм
- Карта (функция высшего порядка)
- Префиксная сумма
- Рекурсивный тип данных
- Оператор сокращения
- Структурная рекурсия
Ссылки
[ редактировать ]- ^ «Модуль Haskell 6: Функции свертки высшего порядка | Антони Диллер» . www.cantab.net . Проверено 4 апреля 2023 г.
- ^ Ричард Берд, «Жемчужины проектирования функциональных алгоритмов», Cambridge University Press, 2010, ISBN 978-0-521-51338-8 , с. 42
- ^ «Array.prototype.reduce() — JavaScript | MDN» . http://developer.mozilla.org . 11 декабря 2023 г. Проверено 16 января 2024 г.
- ^ «fold — язык программирования Kotlin» . Котлин . Джетмозги . Проверено 29 марта 2019 г.
- ^ «reduce — язык программирования Kotlin» . Котлин . Джетмозги . Проверено 29 марта 2019 г.
- ^ «Результат — язык программирования Kotlin» . Котлин . Джетмозги . Проверено 29 марта 2019 г.
- ^
Для справки
functools.reduce:import functools
Для справкиreduce:from functools import reduce - ^ «Итератор в core::iter» . Ржавчина . Команда Руста . Проверено 22 июня 2021 г.
- ^ Одерский, Мартин (5 января 2008 г.). «Re:Блог: Мой вердикт по языку Scala» . Группа новостей : comp.scala.lang . Архивировано из оригинала 14 мая 2015 года . Проверено 14 октября 2013 г.
- ^ Стерлинг, Николас. «Интуитивно понятное использование оператора /: в Scala (foldLeft)» . Проверено 24 июня 2016 г.
- ^ «Fold API — Стандартная библиотека Scala» . www.scala-lang.org . Проверено 10 апреля 2018 г.
- ^ Хаттон, Грэм. «Урок универсальности и выразительности складки» (PDF) . Журнал функционального программирования (9 (4)): 355–372 . Проверено 26 марта 2009 г.
- ^ Папа, Берни. «Как исправить ситуацию с правой стороны» (PDF) . Монада.Читатель (6): 5–16 . Проверено 1 мая 2011 г.