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

В функциональном программировании свертывание ( также называемое сокращением , накоплением , агрегированием , сжатием или внедрением ) относится к семейству функций высшего порядка , которые анализируют рекурсивную . структуру данных и посредством использования данной операции объединения рекомбинируют результаты рекурсивной обработки ее составные части, создавая возвращаемую стоимость. Обычно свертка представлена объединяющей функцией , верхним узлом структуры данных и, возможно, некоторыми значениями по умолчанию, которые будут использоваться при определенных условиях. структуры данных Затем сгиб приступает к объединению элементов иерархии , систематически используя функцию.

Складки в некотором смысле двойственны развертываниям , которые принимают начальное применяют функцию, значение и коркурсивно чтобы решить, как постепенно построить корекурсивную структуру данных, тогда как сгиб рекурсивно разбивает эту структуру, заменяя ее результатами применения объединяющей функции в точке каждый узел по его конечным значениям и рекурсивным результатам ( катаморфизм или анаморфизм развертываний).

По мере структурных преобразований [ править ]

Складки можно рассматривать как последовательную замену структурных компонентов структуры данных функциями и значениями. Списки , например, во многих функциональных языках строятся из двух примитивов: любой список представляет собой либо пустой список, обычно называемый nil ( []), или создается путем добавления префикса элемента перед другим списком, создавая так называемый cons узел ( Cons(X1,Cons(X2,Cons(...(Cons(Xn,nil))))) ), возникающий в результате применения cons функция (записывается через двоеточие (:)в Хаскеле ). можно рассматривать как замену нуля каждого в конце списка определенным значением и замену минуса Складку в списках определенной функцией. Эти замены можно рассматривать в виде диаграммы:

Есть еще один способ последовательно выполнить структурное преобразование, при этом порядок двух звеньев каждого узла меняется при передаче в функцию объединения:

Эти изображения иллюстрируют правый и левый сгиб списка визуально . Они также подчеркивают тот факт, что foldr (:) [] — это функция идентификации в списках ( неглубокая копия на языке Лиспа ), заменяющая cons на cons и ноль с 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  ]   ->   f 
  zfoldl   z   [   ]       =   bfoldl 
  foldl   f   z   (  x  :  xs  )   =   f   (   f  xs   z   x  )   -

Если список пуст, результатом является начальное значение. Если нет, сверните хвост списка, используя в качестве нового начального значения результат применения f к старому начальному значению и первому элементу.

 foldr   ::   (  a   ->   b   ->   b  )   ->   -   >   [  a  ]   ->   f 
  zfoldr   z   [   ]       =   bfoldr 
  xs   f   z   (  x  :  xs  )   =   f   x   (  foldr   f   z   b  )

Если список пуст, результатом является начальное значение z. Если нет, примените f к первому элементу и результату сгиба остальных.

Древовидные складки [ править ]

Списки можно сворачивать в виде дерева, как для конечных, так и для неопределенно определенных списков:

foldt   f   z   [       =   zfoldtfz 
 zfoldifz   foldifz   ]   [  x  ]      =   =   [   = 
 foldtfz   fx   (   fxzfoldtfzxs       )   foldi   :   ]   (  пары   fxs   xs  ) 
 
     (         x   = 
                      ж   z   (  пары   ж   xs  )) 
 
 пары   ж   (  x  :  y  :  t  )    =   f   x   y   :   пары   f   t 
 пары   _   t          =   t

В случае foldi функции, чтобы избежать ее неконтролируемого вычисления в неопределенно определенных списках, функция f должен не всегда требовать значение своего второго аргумента, по крайней мере, не полностью или не сразу (см. пример ниже).

Складки для непустых списков [ править ]

foldl1   f   [  x  ]        =   xfoldl1 
 foldl1   f   (  x  :  y  :  xs  )   =   foldr1   f   (  f   x   y   :   xs  ) 

 foldt1   f   [  x  ]        =   xfoldr1 
 xs   f   (  x  :  xs  )     =   f   x   (  foldr1   f    ) 

 f     [  x  ]        =   xfoldt1 
 f   f   (  x  :  y  :  xs  )   =   foldt1   f   (  f   x   y   :   пары   f   xs  ) 
 
 foldi1   f   [  x  ]        =   xfoldi1 
 )   f   (  x  :  xs  )     =     x   (  foldi1   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")).

Обращение списка также является хвостовой рекурсией (его можно реализовать с помощью 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"   (  карту   показать   [  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   :  )   .foldi   минус   [  5  ,  7  ..  ]   p   .map   (  \  (  x  :  xs  )   ys   ->   :   объединение   xs   ys   )  [   ]  
                        *   p   (  \  p  >   [  x  -  =  ,   п  *  р  +  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: Пустой список»  ) 
 last   =   foldl   (  \  a   x   ->   x  )   (  ошибка   «последний: Пустой список»  )

На разных языках [ править ]

Язык	Левая складка	Правая складка	Левая складка без начального значения	Сгиб вправо без начального значения	Развернуть	Примечания
АПЛ	`func⍨/⌽initval,vector`	`func/vector,initval`	`func⍨/⌽vector`	`func/vector`
С# 3.0	`ienum.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 ...)`		Выражение сгиба (только для шаблонов с переменным числом вариантов ): `op` является бинарным оператором (оба `op`s должны быть одинаковыми, например, `(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.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 initval`	`List.reduce func list` `Seq.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.inject(initval, func)`	`list.reverse().inject(initval, func)`	`list.inject(func)`	`list.reverse().inject(func)`
Хаскелл	`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(initval, func)`		`stream.reduce(func)`
JavaScript 1.8 ECMAScript 5	`array.reduce(func, initval)`^[3]		`array.reduce(func)`
Юлия	`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] что уменьшает `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 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, list`		`reduce block list`			в `List::Util` модуль
PHP	`array_reduce(array, func, initval)`	`array_reduce(array_reverse(array), func, initval)`	`array_reduce(array, func)`	`array_reduce(array_reverse(array), func)`		Когда `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)`
Рубин	`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]
Схема Р ⁶РС	`(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 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)`
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, имеющего определение

 г   []   знак равно   v 
  г   (  Икс  :  Икс  )   знак равно   ж   Икс   (  г   Икс  )

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

 g   =   Foldr   f   v

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

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

См. также [ править ]

Ссылки [ править ]

^ «Модуль 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 г.

Внешние ссылки [ править ]

[1] «Модуль Haskell 6: Функции свертки высшего порядка | Антони Диллер» . www.cantab.net . Проверено 4 апреля 2023 г.

[foldrn-2] Ричард Берд, «Жемчужины проектирования функциональных алгоритмов», Cambridge University Press, 2010, ISBN 978-0-521-51338-8 , с. 42

[3] «Array.prototype.reduce() — JavaScript | MDN» . http://developer.mozilla.org . 11 декабря 2023 г. Проверено 16 января 2024 г.

[4] «fold — язык программирования Kotlin» . Котлин . Джетмозги . Проверено 29 марта 2019 г.

[5] «reduce — язык программирования Kotlin» . Котлин . Джетмозги . Проверено 29 марта 2019 г.

[6] «Результат — язык программирования Kotlin» . Котлин . Джетмозги . Проверено 29 марта 2019 г.

[7] Для справки functools.reduce: import functools
Для справки reduce: from functools import reduce

[8] «Итератор в core::iter» . Ржавчина . Команда Руста . Проверено 22 июня 2021 г.

[9] Одерский, Мартин (5 января 2008 г.). «Re:Блог: Мой вердикт по языку Scala» . Группа новостей : comp.scala.lang . Архивировано из оригинала 14 мая 2015 года . Проверено 14 октября 2013 г.

[10] Стерлинг, Николас. «Интуитивно понятное использование оператора /: в Scala (foldLeft)» . Проверено 24 июня 2016 г.

[11] «Fold API — Стандартная библиотека Scala» . www.scala-lang.org . Проверено 10 апреля 2018 г.

[12] Хаттон, Грэм. «Урок универсальности и выразительности складки» (PDF) . Журнал функционального программирования (9 (4)): 355–372 . Проверено 26 марта 2009 г.

[13] Папа, Берни. «Как исправить ситуацию с правой стороны» (PDF) . Монада.Читатель (6): 5–16 . Проверено 1 мая 2011 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]