Fold

rodzina funkcji wyższego rzędu obliczających pojedynczą wartość na podstawie struktury danych przy pomocy rekurencji

Fold (z ang. składać, zwijać) to rodzina funkcji wyższego rzędu występująca w językach funkcyjnych. Znana jest również 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) i 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. Oba procesy znane są pod nazwami anamorfizm i katamorfizm.

Funkcje fold na listach edytuj

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 problemu 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 często podaje się również 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 edytuj

Jak już było wspomniane, funkcje fold mogą 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 i 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 można 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:

 
diagram operacji foldr

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

 
diagram operacji foldr

Diagramy te ilustrują również pochodzenie słów „lewy” i „prawy” fold. Można również 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 edytuj

W Haskellu funkcje foldr i foldl mogą być zapisane w postaci kilku równań:

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

W powyższym przykładzie jeżeli lista wejściowa jest pusta, wynikiem jest wartość początkowa, w przeciwnym przypadku wywołaj funkcję f na pierwszym elemencie listy i na wyniku rekurencyjnego wywołania foldr.

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

W powyższym przykładzie 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 i lewy fold w języku Scheme mają następujące implementacje, odpowiednio:

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

oraz

(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ę, gdy argumentem dla niej jest lista pusta.

Fold w różnych językach
Language Lewy fold Prawy fold Lewy fold 1[1] Prawy fold 1[1] Uwagi
Haskell foldl func initval list foldr func initval list foldl1 func list foldr1 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
OZ {FoldL List Func Initval} {FoldR List Func Initval}
Python 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))
Python 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)) reduce jest pakiecie functools.

Żeby używać functools.reduce: import functools
Żeby używać reduce: from functools import reduce

Ruby 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)
W Ruby 1.8.7+, można podawać również symbol oznaczający funkcję zamiast bloku
enum to Enumerator
C++ std::accumulate(begin, end, initval, func) std::accumulate(rbegin, rend, initval, func) w nagłówku <numeric>
begin i end to iteratory
Perl reduce block initval, list reduce block list w module List::Util
C# 3.0 ienum.Aggregate(initval, func) ienum.Reverse().Aggregate(initval, func) ienum.Aggregate(func) ienum.Reverse().Aggregate(func) Aggregate jest rozszerzeniem typu
ienum jest typu IEnumerable
Konstrukcja analogiczna dla pozostałych języków .NET
Java 8+ stream.reduce(initval, func) stream.reduce(func)
JavaScript 1.8 array.reduce(func, initval) array.reduceRight(func, initval) array.reduce(func) array.reduceRight(func)
Common Lisp (reduce func list :initial-value initval) (reduce func list :from-end t :initial-value initval) (reduce func list) (reduce func list :from-end t) func to symbol
Scheme R6RS (fold-left func initval list) (fold-right func initval list)
Smalltalk collection inject: value into: [ :value :each | ... ]
Erlang lists:foldl(Fun, Accumulator, List) lists:foldr(Fun, Accumulator, List)
PHP array_reduce(array, func, initval) array_reduce(array, func) initval czyli wartość początkowa może być jedynie typu integer. Kiedy nie ma initval używany jest NULL, więc nie jest to wersja foldl1.
Scala list.foldLeft(initval)(func) list.foldRight(initval)(func) list.reduceLeft(func) list.reduceRight(func)
Mathematica Fold[func, initval, list] Fold[func, initval, Reverse[list]] Fold[func, list] Fold[func, Reverse[list]] Fold bez wartości początkowej jest obsługiwany dla wersji 10.0 i wyższej
Maple foldl(func, initval, sequence) foldr(func, initval, sequence)
Julia[2] foldl(op, itr; [init]) foldr(op, itr; [init]) foldl(op, itr) foldr(op, itr)

Kolejność ewaluacji edytuj

Jeżeli w języku występuje 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 i rekurencja ogólna ulegnie zatrzymaniu. Z tego powodu foldr można wywoływać na nieskończonych listach. Z drugiej strony foldl na listach nieskończonych uległby zapętleniu.

Kolejną kwestią, która pojawia 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 niektóre 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, gdy nie znamy elementu neutralnego funkcji f, bądź chcemy aby operacja wykonywana była jedynie na elementach zadanej listy, bez dodatkowej wartości początkowej, wówczas mamy do dyspozycji odmiany foldr i foldl. Foldr1 i foldl1 używają odpowiednio ostatniego i 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 edytuj

Odwrócenie listy:

rev = foldl (\ys x -> x : ys) [] -- Haskell
(reduce (fn [ys x] (cons x ys)) () coll) ; Clojure

gdzie (\ys x -> x : ys) i (fn [ys x] (cons x ys)) to funkcje, które zwracają listę ys z elementem x na początku.

Funkcja wyższego rzędu map:

map f = foldr ((:) . f) [] -- Haskell
(defn map [f coll] (reduce 
    (fn [ys x] (cons (f x) ys)) () (reverse coll))) ; Clojure

gdzie kropka (.) to operator składania funkcji, a dwukropek (:) to tworzenie listy (cons). Clojure nie posiada funkcji reduce-right/foldr, ale wywołanie reverse przynosi ten sam efekt.

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"]

Zobacz też edytuj

Przypisy edytuj

  1. a b „Lewy fold 1” oraz „prawy fold 1” to odmiany odpowiednich foldów, które nie pobierają wartości początkowej jako argumentu. Pierwsza wykonywana operacja pobiera jako argumenty dwa pierwsze elementy listy. Z tego powodu nie można tych odmian stosować na listach pustych, zaś typ funkcji łączącej ograniczony jest do (a, a) -> a, co oznacza, że oba argumenty oraz wynik muszą być tego samego typu. Obie odmiany mają swoje zastosowania np. przy konkatenacji napisów.
  2. Collections and Data Structures · The Julia Language [online], docs.julialang.org [dostęp 2023-06-09].

Linki zewnętrzne edytuj