Fold

Fold (z ang. składać, zwijać) to rodzina funkcji wyższego rzędu występująca w językach funkcyjnych. Znana jest także jako reduce, accumulate, compress bądź inject. Funkcje fold przetwarzają uporządkowane kolekcje danych (zazwyczaj listy) w celu zbudowania końcowego wyniku przy pomocy jakiejś funkcji łączącej elementy. Dwie najbardziej popularne funkcje z tej rodziny to foldr (fold right) oraz foldl (fold left)

Funkcje fold są w pewnym sensie dualne do funkcji z rodziny unfold, które z pojedynczej wartości oraz zadanej funkcji generują kolekcję danych. Fold zaś z kolekcji danych, przy pomocy zadanej funkcji, generuje pojedynczy wynik. Obydwa procesy znane są pod nazwami anamorfizm oraz katamorfizm.

Funkcje fold na listach

Zastosowanie funkcji z rodziny fold na liście [1,2,3,4,5], wraz z operatorem dodawania da wynik 15, czyli sumę wszystkich elementów tej listy. Do pewnego stopnia fold na liście działa tak, jakby zastępował przecinki zadanym operatorem. W omawianym tu przypadku, rezultatem byłoby 1+2+3+4+5

W powyższym przykładzie nie użyto nawiasów, lecz dla operatora dodawania (który jest łączny) nie ma to znaczenia. Jednakże w przypadku wielu funkcji, chociażby odejmowania, fakt rozmieszczenia nawiasów, a przez to kolejności wykonywania operacji, ma istotne znaczenie. Dwa podstawowe podejścia do dylematu to łączenie rekurencyjnie od pierwszego elementu (określane jako prawy fold czyli foldr), oraz rekurencyjne łączenie elementów rozpoczynając od ostatniego (lewy fold, czyli foldl). W naszym przykładzie foldr ustawiłby nawiasy w następujący sposób: 1 + (2 + (3 + (4 + 5))). Dla foldl ustawienie nawiasów byłoby następujące: (((1 + 2) + 3) + 4) + 5

Dotychczas mowa była tylko o dwóch parametrach początkowych dla funkcji z rodziny fold, ale wielokrotnie głosi się także trzeci argument: wartość początkową, do której dołączane są elementy listy. Jeżeli w powyższym przykładzie jako wartość początkową ustawiono by liczbę 0, foldr wykonałby działania zgodnie z notacją 1 + (2 + (3 + (4 + (5 + 0)))), zaś foldl: ((((0 + 1) + 2) + 3) + 4) + 5.

Zwijanie list jako operacja strukturalna

Jak już było wspomniane, funkcje fold potrafią działać na zasadzie przypominającej zamianę przecinków na operatory. W rzeczywistości jest to bliższe zamianie komponentów tworzących strukturę funkcjami oraz wartościami, postępując w uporządkowany odgórnie sposób. W większości języków programowania lista jest albo listą pustą (w informatyce najczęściej oznaczaną przez nil), bądź też jest to wynik dołączenia pewnego elementu do końca istniejącej listy (oznaczane zwykle jako cons). W języku Haskell lista pusta oznaczana jest jako [], zaś operacja cons oznaczana jest symbolem (:) (dwukropek). W takim zapisie lista [1,2,3,4,5] ma postać: 1:2:3:4:5:[]. Wówczas da się spojrzeć na funkcję foldr jako formę "zamiany" nil na końcu listy wartością początkową, zaś operacji cons - konkretną funkcją. Najprościej ilustruje to poniższy diagram:

Dla foldl wartość początkowa zastąpiłaby nil umieszczony na początku listy, co prezentuje kolejny diagram:

Diagramy te ilustrują także pochodzenie słów "lewy" oraz "prawy" fold. Można także zaobserwować, że wywołanie foldr (:) [] to funkcja identycznościowa na liście, każda lista przekazana jako parametr do tego wywołania, zostanie zwrócona jako wynik w niezmienionym kształcie.

Implementacja

W Haskellu funkcje 'foldr oraz foldl bywają zapisane w postaci kilku równań:

foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

Oznacza to, że jeżeli lista wejściowa jest pusta, wynikiem jest wartość początkowa, w przeciwnym przypadku wywołaj funkcję f na pierwszym elemencie listy oraz na wyniku rekurencyjnego wywołania foldr

foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

Jeżeli lista wejściowa jest pusta, wynikiem jest wartość początkowa, w przeciwnym przypadku wywołaj foldl z nową wartością początkową powstałą z wywołania funkcji f na poprzedniej wartości początkowej oraz na pierwszym elemencie listy

W języku Scheme oraz innych pochodnych Lispa pustą listę, oraz operator składania listy reprezentuje się oznaczeniami: () oraz cons. Prawy oraz lewy fold w języku Scheme posiadają następującą implementację:

(define (foldr f z xs)
 (if (null? xs)
  z
  (f (car xs) (foldr f z (cdr xs)))))

(define (foldl f z xs)
 (if (null? xs)
  z
  (foldl f (f (car xs) z) (cdr xs))))

Gdzie null? oznacza funkcję predykatów zwracającą prawdę, kiedy argumentem dla niej jest lista pusta.

Kolejność ewaluacji

Jeżeli w języku jest leniwa ewaluacja, foldr od razu zwróci wynik wywołania funkcji f na rekurencyjnym wołaniu foldr. Przy czym jeżeli f może obliczyć wynik nie korzystając z wyniku wewnętrznej rekurencji, nie będzie ona przetwarzana oraz rekurencja ogólna ulegnie zatrzymaniu. Z tego powodu foldr da się wywoływać na nieskończonych listach. Z drugiej strony foldl na listach nieskończonych uległby zapętleniu.

Kolejną kwestią, która ukazuje się przy leniwej ewaluacji lewych foldów, jest to, że wartość początkowa nie jest obliczana, zanim nie zostanie wywołana rekurencja. Może to doprowadzić do przepełnienia stosu, jeżeli po przejrzeniu długiej listy trzeba jeszcze obliczyć wielkie wyrażenie. Z tego powodu pewne języki wprowadzają ograniczenia na foldl wymuszające ewaluację wartości początkowej przed przystąpieniem do rekurencji. W języku Haskell taką funkcjonalność realizuje foldl' (gdzie apostrof oznacza prime) dostępna w bibliotece Data.List

W sytuacji, kiedy nie znamy elementu neutralnego funkcji f, bądź chcemy aby operacja wykonywana była zaledwie na elementach zadanej listy, bez dodatkowej wartości początkowej, wówczas mamy do dyspozycji odmiany foldr oraz foldl. Foldr1 oraz foldl1 używają odpowiednio ostatniego oraz pierwszego elementu listy w miejsce wartości początkowej. 1 w nazwie odnosi się m.in. do minimalnej wielkości listy (przynajmniej 1 element).

Przykłady

Odwrócenie listy:

rev = foldl (\ys x -> x : ys) []

gdzie (\ys x -> x : ys) jest λ - funkcją

Funkcja wyższego rzędu map:

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

gdzie kropka (.) to operator składania funkcji.

Złączenie napisów aby uzyskać: "(f 1 (f 2 (f 3 (f 4 (f 5 z)))))"

foldr (\x y -> concat ["(f ",x," ",y,")"]) "z" ["1","2","3","4","5"]

Złączenie napisów aby uzyskać: "(f (f (f (f (f z 1) 2) 3) 4) 5)"

foldl (\x y -> concat ["(f ",x," ",y,")"]) "z" ["1","2","3","4","5"]

Sprawdź też

• Homomorfizm
• Funkcje wyższego rzędu
• Programowanie funkcyjne

Przypisy

Linki zewnętrzne

• Przykłady wywołań funkcji fold w Haskellu
• "Funkcje wyższego rzędu — map, fold oraz filter"
• "Unit 6: The Higher-order fold Functions"
• "Opis funkcji fold"
• Różnice pomiędzy foldr a foldl.
• "Constructing List Homomorphism from Left and Right Folds"
• "The magic foldr"