Składanie (funkcja wyższego rzędu) - Fold (higher-order function)

W programowania funkcjonalnego , krotnie (zwane także zmniejszyć , nagromadzenia , kruszywo , kompres lub inject ) odnosi się do rodziny funkcje wyższego rzędu , które analizują do rekurencyjnego struktury danych oraz przez wykorzystanie danego łączący operacji rekombinacji wyniki rekurencyjnie przetwarzającego części składowe, budowanie wartości zwracanej. Typowo, pokrywa jest przedstawiona z łączącego funkcję , górną węzła o strukturze danych , i ewentualnie z pewnymi wartościami domyślnymi do wykorzystania w pewnych warunkach. Zakładka następnie przystępuje do łączenia elementów hierarchii struktury danych , wykorzystując funkcję w sposób systematyczny.

Fałdy są w pewnym sensie podwójnego do rozwija , które odbywają się nasion wartość i zastosowanie funkcji corecursively do decydowania, jak stopniowo zbudować corecursive strukturę danych, podczas gdy krotnie rekurencyjnie przerwy, że struktura w dół, zastępując go z wynikami stosowania funkcję łączenia co każdy węzeł na jego końcowych wartościach i rekurencyjnych wynikach ( katamorfizm , kontra anamorfizm rozwijania).

Jako przekształcenia strukturalne

Fałdy można uznać za konsekwentne zastępowanie elementów strukturalnych struktury danych funkcjami i wartościami. Listy , na przykład, budowane są w wielu językach funkcyjnych z dwóch pierwotnych: każda lista jest albo pusta lista, powszechnie nazywane zero   ( []) lub jest wykonana poprzedzając element przed innym liście, tworząc tak zwany minusy  węzeł (  Cons(X1,Cons(X2,Cons(...(Cons(Xn,nil))))) ), wynikające z zastosowania consfunkcji (zapisanej jako dwukropek (:) w Haskell ). Można zobaczyć fałdę na listach jako zastępując   na zero na końcu listy o wartości określonej, i zastępując każdy minusy z funkcji konkretnego. Te zamienniki można zobaczyć w postaci diagramu:

Istnieje inny sposób przeprowadzenia transformacji strukturalnej w spójny sposób, z odwróceniem kolejności dwóch łączy każdego węzła po wprowadzeniu do funkcji łączenia:

Te zdjęcia ilustrują wizualnie prawy i lewy fałd listy . Podkreślają również fakt, że foldr (:) []jest to funkcja tożsamości na listach (a płytkie kopiowania w Lisp żargonie), jak wymiana minusy z consoraz zerowa ze nilnie zmieni rezultatu. Diagram składania w lewo sugeruje prosty sposób odwrócenia listy, foldl (flip (:)) []. Zauważ, że parametry przeciw muszą być odwrócone, ponieważ element do dodania jest teraz prawym parametrem funkcji łączenia. Innym łatwym rezultatem do zobaczenia z tego punktu widzenia jest napisanie funkcji mapy wyższego rzędu w kategoriach foldr, przez złożenie funkcji działającej na elementach z cons, jako:

 map f = foldr ((:) . f) []

gdzie kropka (.) jest operatorem oznaczającym złożenie funkcji .

Ten sposób patrzenia na rzeczy zapewnia prostą drogę do projektowania funkcji fałdowych na innych algebraicznych typach danych i strukturach, takich jak różnego rodzaju drzewa. Jeden pisze funkcję, która rekursywnie zastępuje konstruktory typu danych dostarczonymi funkcjami, a wszelkie stałe wartości typu podanymi wartościami. Taka funkcja jest ogólnie nazywana katamorfizmem .

Na listach

Złożenie listy [1,2,3,4,5]z operatorem dodawania dałoby 15, sumę elementów listy [1,2,3,4,5]. W przybliżeniu, można pomyśleć o tym złożeniu jako zamianie przecinków na liście na operację +, dając 1 + 2 + 3 + 4 + 5.

W powyższym przykładzie + jest operacją asocjacyjną , więc wynik końcowy będzie taki sam niezależnie od nawiasów, chociaż specyficzny sposób jego obliczenia będzie inny. W ogólnym przypadku binarnych funkcji nieasocjacyjnych kolejność łączenia elementów może mieć wpływ na wynik końcowy. Na listach można to zrobić na dwa oczywiste sposoby: albo łącząc pierwszy element z wynikiem rekursywnego łączenia pozostałych (tzw. right fold ), albo łącząc wynik rekursywnego łączenia wszystkich elementów oprócz ostatniego, z ostatni element (nazywany lewą fałdą ). Odpowiada to operatorowi binarnemu , który jest prawostronnie lub lewostronnie zespolony, w terminologii Haskella lub Prologa . W przypadku prawego zgięcia suma zostanie umieszczona w nawiasach jako 1 + (2 + (3 + (4 + 5))), podczas gdy przy lewym zgięciu będzie ona umieszczona w nawiasach jako (((1 + 2) + 3) + 4) + 5.

W praktyce wygodnie i naturalnie jest mieć wartość początkową, która w przypadku zgięcia w prawo jest używana na końcu listy, a w przypadku zgięcia w lewo jest to, co początkowo łączy się z pierwszym elementem Lista. W powyższym przykładzie wartość 0 ( tożsamość dodatku ) zostałaby wybrana jako wartość początkowa, dająca 1 + (2 + (3 + (4 + (5 + 0))))dla fałdy prawej i ((((0 + 1) + 2) + 3) + 4) + 5dla lewej fałdy. W przypadku mnożenia początkowy wybór 0 nie zadziała: 0 * 1 * 2 * 3 * 4 * 5 = 0. Element tożsamości do mnożenia to 1. To dałoby nam wynik 1 * 1 * 2 * 3 * 4 * 5 = 120 = 5!.

Fałdy liniowe a drzewopodobne

Użycie wartości początkowej jest konieczne, gdy funkcja łącząca f   jest niesymetryczna w swoich typach (np. a → b → b), tj. gdy typ jej wyniku jest inny niż typ elementów listy. Następnie należy użyć wartości początkowej tego samego typu co  wynik f , aby możliwy był liniowy łańcuch aplikacji. To, czy będzie on zorientowany w lewo, czy w prawo, zależy od typów oczekiwanych od jego argumentów przez funkcję łączącą. Jeśli jest to drugi argument, który musi być tego samego typu co wynik, wtedy f   może być postrzegane jako operacja binarna, która kojarzy się po prawej stronie i na odwrót.

Gdy funkcja jest magmą , czyli symetryczną w swoich typach ( a → a → a), a typ wyniku jest taki sam jak typ elementów listy, nawiasy można umieszczać w dowolny sposób tworząc drzewo zagnieżdżonych podwyrażeń, np ((1 + 2) + (3 + 4)) + 5. . Jeśli operacja binarna f   jest asocjacyjna, wartość ta będzie dobrze zdefiniowana, tj. taka sama dla każdego nawiasu, chociaż szczegóły operacyjne dotyczące sposobu jej obliczania będą inne. Może to mieć znaczący wpływ na wydajność, jeśli f   jest nieścisłe .

Natomiast fałdy liniowych to węzeł zorientowanych i działać w sposób spójny dla każdego węzła z listy , drzewa jak fałdy są całe listy zorientowane i działać w sposób spójny grup węzłów.

Specjalne fałdy dla niepustych list

Często chce się wybrać element tożsamości operacji f jako wartość początkową z . Gdy żadna wartość początkowa nie wydaje się odpowiednia, na przykład, gdy chce się zwinąć funkcję, która oblicza maksimum swoich dwóch parametrów na niepustej liście, aby uzyskać maksymalny element listy, istnieją warianty foldri foldlktóre używają ostatniego i pierwszy element listy odpowiednio jako wartość początkowa. W Haskell i kilku innych językach nazywa się je foldr1i foldl1, przy czym 1 odnosi się do automatycznego dostarczania początkowego elementu oraz do faktu, że listy, do których są stosowane, muszą zawierać co najmniej jeden element.

Te fałdy używają operacji binarnych symetrycznych pod względem typu: typy obu argumentów i wynik muszą być takie same. Richard Bird w swojej książce z 2010 roku proponuje „ogólną funkcję składania na niepustych listach”, foldrnktóra przekształca swój ostatni element, stosując do niego dodatkową funkcję argumentu, na wartość typu wyniku przed rozpoczęciem samego składania, a zatem jest w stanie aby użyć asymetrycznej operacji binarnej typu, takiej jak zwykła, w foldrcelu uzyskania wyniku typu innego niż typ elementów listy.

Realizacja

Fałdy liniowe

Haskell używając jako przykład foldli foldrmoże być wytwarzane w kilku równań.

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

Jeśli lista jest pusta, wynikiem jest wartość początkowa. Jeśli nie, złóż ogon listy, używając jako nowej wartości początkowej wyniku zastosowania f do starej wartości początkowej i pierwszego elementu.

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

Jeśli lista jest pusta, wynikiem jest wartość początkowa z. Jeśli nie, zastosuj f do pierwszego elementu i wynik zwijania reszty.

Fałdy przypominające drzewo

Listy można zwijać w sposób podobny do drzewa, zarówno w przypadku list skończonych, jak i nieskończenie zdefiniowanych:

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

W przypadku foldifunkcji, aby uniknąć jej niekontrolowanej oceny na nieskończenie zdefiniowanych listach, funkcja nief musi zawsze żądać wartości drugiego argumentu, przynajmniej nie całej, lub nie od razu (patrz przykład poniżej).

Fałdy dla niepustych list

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))

Uwagi dotyczące zamówienia oceny

W przypadku leniwej lub nieścisłej oceny foldrnatychmiast zwróci zastosowanie f do nagłówka listy i rekurencyjny przypadek zawinięcia nad resztą listy. Tak więc, jeśli f jest w stanie wytworzyć jakąś część swojego wyniku bez odniesienia do przypadku rekurencyjnego po swojej „prawej” stronie, tj. w swoim drugim argumencie, a reszta wyniku nigdy nie jest wymagana, wówczas rekurencja się zatrzyma (np. ) . Pozwala to prawo folds działać na nieskończonych listach. Natomiast natychmiast wywoła się z nowymi parametrami, aż dotrze do końca listy. Ta tail rekursja może być wydajnie skompilowana jako pętla, ale nie radzi sobie w ogóle z nieskończonymi listami — będzie się powtarzać w nieskończonej pętli . head == foldr (\a b->a) (error "empty list")foldl

Po dojściu do końca listy, wyrażenie jest w efekcie budowane przez foldlzagnieżdżone aplikacje pogłębiające w lewo f, które jest następnie prezentowane wywołującemu do oceny. Gdyby funkcja fodwoływała się najpierw do swojego drugiego argumentu tutaj i byłaby w stanie wytworzyć pewną część swojego wyniku bez odniesienia do przypadku rekurencyjnego (tutaj, po lewej stronie, tj. w swoim pierwszym argumencie), wówczas rekurencja zatrzymałaby się. Oznacza to, że chociaż występuje foldrrekursywnie po prawej stronie , pozwala to funkcji leniwego łączenia na sprawdzanie elementów listy od lewej; i odwrotnie, podczas foldlrekurencji po lewej stronie pozwala funkcji leniwego łączenia na sprawdzenie elementów listy z prawej strony, jeśli tak zdecyduje (np . ). last == foldl (\a b->b) (error "empty list")

Odwracanie listy jest również tail-recursive (można to zaimplementować za pomocą ). Na listach skończonych oznacza to, że składanie w lewo i odwracanie mogą być złożone, aby wykonać składanie w prawo w sposób rekurencyjny (por.  ), z modyfikacją funkcji, aby odwróciła kolejność jej argumentów (tj. ), tail-rekursywne budowanie reprezentacji ekspresji, którą zbudowałaby prawa strona. Zewnętrzna struktura listy pośredniej może zostać wyeliminowana za pomocą techniki stylu z przekazywaniem kontynuacji ; podobnie, (  jest potrzebne tylko w językach takich jak Haskell z odwróconą kolejnością argumentów do funkcji łączenia, inaczej niż np. w Scheme, gdzie ta sama kolejność argumentów jest używana do łączenia funkcji do obu i ). 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

Inną kwestią techniczną jest to, że w przypadku lewych fałd przy użyciu oceny z opóźnieniem, nowy parametr początkowy nie jest oceniany przed wykonaniem wywołania rekurencyjnego. Może to prowadzić do przepełnienia stosu, gdy ktoś dotrze do końca listy i spróbuje ocenić wynikowe potencjalnie gigantyczne wyrażenie. Z tego powodu takie języki często zapewniają bardziej rygorystyczny wariant składania w lewo, co wymusza ocenę początkowego parametru przed wykonaniem wywołania rekurencyjnego. W Haskell jest to foldl'(zwróć uwagę na apostrof, wymawiany 'prim') funkcja w Data.Listbibliotece (trzeba jednak zdawać sobie sprawę, że wymuszenie wartości zbudowanej za pomocą leniwego konstruktora danych nie wymusi automatycznie jej składników). W połączeniu z rekurencją ogona fałdy takie zbliżają się do wydajności pętli, zapewniając ciągłą pracę w przestrzeni, gdy leniwa ocena końcowego wyniku jest niemożliwa lub niepożądana.

Przykłady

Korzystając z interpretera Haskella , strukturalne przekształcenia, które wykonują funkcje fold, można zilustrować, konstruując ciąg:

λ> 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))))"

Nieskończone zwijanie drzewiaste jest demonstrowane np. w produkcji rekurencyjnych liczb pierwszych przez nieograniczone sito Eratostenesa w 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 . ...

gdzie funkcja uniondziała na listach uporządkowanych w lokalnej sposób efektywnie produkować swój zestaw unii i minusich różnicę set .

W przypadku list skończonych, np. sortowanie przez scalanie (i jego odmiana z usuwaniem duplikatów, nubsort) można łatwo zdefiniować za pomocą składania drzewiastego jako

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

z funkcją mergewariant z zachowaniem duplikatów union.

Funkcje headi lastmogły zostać zdefiniowane poprzez składanie jako

head = foldr (\x r -> x) (error "head: Empty list")
last = foldl (\a x -> x) (error "last: Empty list")

W różnych językach

Uniwersalność

Fold jest funkcją polimorficzną . Dla każdego g mającego definicję

 g [] = v
 g (x:xs) = f x (g xs)

wtedy g można wyrazić jako

 g = foldr f v

Ponadto, w leniwym języku z nieskończonymi listami, kombinator stałoprzecinkowy można zaimplementować za pomocą fold, udowadniając, że iteracje można zredukować do foldów:

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

Zobacz też

• Funkcja agregująca
• Iterowana operacja binarna
• Katamorfizm , uogólnienie fałd
• Homomorfizm
• Mapa (funkcja wyższego rzędu)
• Suma przedrostka
• Rekurencyjny typ danych
• Operator redukcji
• Rekurencja strukturalna

Bibliografia

Zewnętrzne linki

• "Funkcje wyższego rzędu — mapowanie, składanie i filtrowanie"
• „Jednostka 6: Funkcje składania wyższego rzędu”
• „Złóż w Tcl”
• „Konstruowanie homomorfizmu listy z fałd lewych i prawych”
• „Magiczny folder”