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

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

Эти изображения иллюстрируют правый и левый сгиб списка визуально. Они также подчеркивают тот факт, что foldr (:)является функцией идентификации в списках (неглубокая копия на языке Lisp ), поскольку вместо cons на consи nil с 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.

В приведенном выше примере + - это ассоциативная операция, поэтому конечный результат будет одинаковым независимо от скобок, хотя конкретный способ его вычисления будет другим. В общем случае неассоциативных бинарных функций порядок, в котором объединяются элементы, может влиять на значение окончательного результата. В списках есть два очевидных способа сделать это: либо комбинируя первый элемент с результатом рекурсивного комбинирования остальных (так называемый правый сгиб ), либо комбинируя результат рекурсивного комбинирования всех элементов. но последний, с последним элементом (называемым левой складкой ). В терминологии 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 нестрогий.

, тогда как линейные складки ориентированы на узлы и работают согласованно для каждого узла из list, древовидные свертки ориентированы на весь список и работают согласованно для всех групп узлов.

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

Часто требуется выбрать элемент идентичности операции f в качестве начального значения z. Когда исходное значение не кажется подходящим, например, когда кто-то хочет свернуть функцию, которая вычисляет максимум из двух ее параметров по непустому списку, чтобы получить максимальный элемент списка, существуют варианты foldrи foldl, которые используют последний и первый элементы списка соответственно в качестве начального значения. В Haskell и некоторых других языках они называются foldr1и foldl1, где 1 ссылается на автоматическое предоставление начального элемента и тот факт, что списки, к которым они применяются, должны иметь хотя бы один элемент.

В этих свертках используется симметричная по типу двоичная операция: типы ее аргументов и ее результат должны быть одинаковыми. Ричард Берд в своей книге 2010 года предлагает "общую функцию сворачивания непустых списков" foldrn, которая преобразует свой последний элемент, применяя к нему дополнительную функцию аргумента, в значение типа результата перед запуском сворачивание самого себя и, таким образом, может использовать двоичную операцию с асимметричным типом, такую ​​как обычный foldr, для получения результата, тип которого отличается от типа элементов списка.

Реализация

Линейные свертки

Используя Haskell в качестве примера, foldlи foldrможно сформулировать в виде нескольких уравнений.

foldl :: (b ->a ->b) ->b ->[a] ->b foldl fz = z foldl fz (x: xs) = foldl f (fzx) xs

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

foldr :: (a ->b ->b) ->b ->[a] ->b foldr fz = z foldr fz (x: xs) = fx (foldr fz xs)

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

Древовидные складки

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

foldt fz = z foldt fz [x] = fxz foldt fz xs = foldt fz (пары f xs) foldi fz = z foldi fz (x: xs) = fx (foldi fz (пары f xs)) пары f (x: y: t) = fxy: пары ft пары _ t = t

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

Сворачивание непустых списков

foldl1 f [x] = x foldl1 f (x: y: xs) = foldl1 f (fxy: xs) foldr1 f [x] = x foldr1 f (x : xs) = fx (foldr1 f xs) foldt1 f [x] = x foldt1 f (x: y: xs) = foldt1 f (fxy: пары f xs) foldi1 f [x] = x foldi1 f (x: xs) = fx (foldi1 f (pair f xs))

Рекомендации по порядку оценки

При ленивом или нестрогом вычислении, foldrнемедленно вернет применение f в начало списка и рекурсивный случай сворачивания по остальной части списка. Таким образом, если f может произвести некоторую часть своего результата без ссылки на рекурсивный случай в его «правом», то есть во втором аргументе, а остальная часть результата никогда не требуется, то рекурсия остановится (например, head == foldr (\ a b->a) (ошибка «пустой список»)). Это позволяет правым сверткам работать с бесконечными списками. Напротив, foldlнемедленно вызовет себя с новыми параметрами, пока не достигнет конца списка. Эту хвостовую рекурсию можно эффективно скомпилировать как цикл, но она вообще не может иметь дело с бесконечными списками - она ​​будет рекурсивно повторяться бесконечно в бесконечном цикле.

. выражение фактически построено foldlвложенными углубляющимися влево f-приложениями, которые затем представляются вызывающей стороне для оценки. Если бы функция fсначала ссылалась здесь на свой второй аргумент и могла бы произвести некоторую часть своего результата без ссылки на рекурсивный случай (здесь, слева, т.е. в своем первом аргументе), тогда рекурсия остановится. Это означает, что, хотя foldrвыполняет рекурсию справа, это позволяет функции ленивого комбинирования проверять элементы списка слева; и наоборот, в то время как foldlрекурсирует слева, это позволяет функции ленивого комбинирования проверять элементы списка справа, если она того пожелает (например, last == foldl (\ a b->б) (ошибка «пустой список»)).

Обращение списка также является хвостовой рекурсией (это можно реализовать с помощью rev = foldl (\ ys x ->x: ys)). В конечных списках это означает, что левый и обратный складки могут быть составлены для выполнения правого сворачивания хвостовой рекурсией (см. 1 +>(2 +>(3+>0)) == (( 0 <+3)<+2)<+1) с модификацией функции f, так что она меняет порядок своих аргументов (т. Е. foldr fz == foldl (flip f) z. Foldl (flip (:))), рекурсивно построение представления выражения, которое будет строиться при свертывании вправо. Посторонняя структура промежуточного списка может быть устранена с помощью метода передачи стиля, foldr fz xs = = foldl (\ k x->k. fx) id xs z; аналогично, foldl fz xs == foldr (\ x k->k. flip fx) id xs z(flipтребуется только в таких языках, как Haskell, с его перевернутым порядком аргументов для функции объединения foldl, в отличие, например, от Scheme, где один и тот же порядок аргументов используется для объединения функций для обоих foldlи foldr).

Другой технический момент заключается в том, что в случае левых складок с помощью ленивого вычисления n, новый начальный параметр не оценивается до выполнения рекурсивного вызова. Это может привести к переполнению стека, когда кто-то достигает конца списка и пытается оценить результирующее потенциально гигантское выражение. По этой причине такие языки часто предоставляют более строгий вариант сворачивания влево, который заставляет вычислять начальный параметр перед выполнением рекурсивного вызова. В Haskell это функция foldl '(обратите внимание на апостроф, произносится как «prime») в библиотеке Data.List(нужно помнить о том, что принуждение значения построенный с помощью ленивого конструктора данных, сам по себе не заставит его составляющие автоматически). В сочетании с хвостовой рекурсией такие складки приближаются к эффективности циклов, обеспечивая постоянную пространственную операцию, когда ленивая оценка конечного результата невозможна или нежелательна.

Примеры

Используя интерпретатор Haskell, структурные преобразования, выполняемые функциями свертки, можно проиллюстрировать построением строки:

λ>foldr (\ xy ->concat ["(", x, "+", y, ")"]) "0" (отображение карты [1..13]) "(1+ (2+ (3+ (4+ (5+ (6 + (7+ (8+ (9+ (10+ (11+ (12+ (13 + 0)))))))))))) "λ>foldl (\ xy ->concat [" (", x, "+", y, ")"]) "0" (показать карту [1..13]) "(((((((((((((0 + 1) +2) +3)) +4) +5) +6) +7) +8) +9) +10) +11) +12) +13) "λ>foldt (\ xy ->concat [" (", x," + ", y,") "])" 0 "(показать карту [1..13])" (((((1 + 2) + (3 + 4)) + ((5 + 6) + (7+ 8))) + (((9 + 10) + (11 + 12)) + 13)) + 0) "λ>foldi (\ xy ->concat [" (", x," + ", y,") "])" 0 "(показать карту [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. грамм. грамм. грамм....

, где функция union работает с упорядоченными списками локально, чтобы эффективно создавать их set union и минус их разница между наборами.

Для конечных списков, например, сортировка слиянием (и ее разновидность удаления дубликатов, nubsort) может быть легко определена с использованием древовидной свертки как

mergesort xs = foldt merge [[x] | x <- xs] nubsort xs = foldt union [[x] | x <- xs]

с функцией merge вариант с сохранением дубликатов union.

Функции headи lastмогли были определены путем сворачивания как

head = foldr (\ xr ->x) (ошибка "head: Empty list") last = foldl (\ ax ->x) (error "last: Empty list")

Fold - это полиморфная функция. Для любого g, имеющего определение

g = vg (x: xs) = fx (g xs)

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

g = foldr fv

Кроме того, фиксированная точка комбинатор может быть реализован через свертку, доказывая, что итерации можно свести к сверткам:

yf = foldr (\ _ ->f) undefined (repeat undefined)

• Агрегатная функция
• Итерированная бинарная операция
• Катаморфизм, обобщение складки
• Гомоморфизм
• Карта (функция высшего порядка)
• Префиксная сумма
• Рекурсивный тип данных
• Оператор редукции
• Структурная рекурсия

• «Функции высшего порядка - отображение, сворачивание и фильтрация»
• «Блок 6: Функции сворачивания высшего порядка»
• «Сворачивание в Tcl»
• «Построение гомоморфизма списка из левых и правых складок»
• «Волшебное складывание»