b'\n_START_ARTICLE_\nFold\n_START_SECTION_\nFunkcje fold na listach\n_START_PARAGRAPH_\nZastosowanie funkcji z rodziny fold na li\xc5\x9bcie [1,2,3,4,5], wraz z operatorem dodawania da wynik 15, czyli sum\xc4\x99 wszystkich element\xc3\xb3w tej listy. Do pewnego stopnia fold na li\xc5\x9bcie dzia\xc5\x82a tak, jakby zast\xc4\x99powa\xc5\x82 przecinki zadanym operatorem. W omawianym tu przypadku, rezultatem by\xc5\x82oby 1+2+3+4+5_NEWLINE_W powy\xc5\xbcszym przyk\xc5\x82adzie nie u\xc5\xbcyto nawias\xc3\xb3w, lecz dla operatora dodawania (kt\xc3\xb3ry jest \xc5\x82\xc4\x85czny) nie ma to znaczenia. Jednak\xc5\xbce w przypadku wielu funkcji, chocia\xc5\xbcby odejmowania, fakt rozmieszczenia nawias\xc3\xb3w, a przez to kolejno\xc5\x9bci wykonywania operacji, ma istotne znaczenie. Dwa podstawowe podej\xc5\x9bcia do problemu to \xc5\x82\xc4\x85czenie rekurencyjnie od pierwszego elementu (okre\xc5\x9blane jako prawy fold czyli foldr), oraz rekurencyjne \xc5\x82\xc4\x85czenie element\xc3\xb3w rozpoczynaj\xc4\x85c od ostatniego (lewy fold, czyli foldl). W naszym przyk\xc5\x82adzie foldr ustawi\xc5\x82by nawiasy w nast\xc4\x99puj\xc4\x85cy spos\xc3\xb3b: 1 + (2 + (3 + (4 + 5))). Dla foldl ustawienie nawias\xc3\xb3w by\xc5\x82oby nast\xc4\x99puj\xc4\x85ce: (((1 + 2) + 3) + 4) + 5_NEWLINE_Dotychczas mowa by\xc5\x82a tylko o dw\xc3\xb3ch parametrach pocz\xc4\x85tkowych dla funkcji z rodziny fold, ale cz\xc4\x99sto podaje si\xc4\x99 r\xc3\xb3wnie\xc5\xbc trzeci argument: warto\xc5\x9b\xc4\x87 pocz\xc4\x85tkow\xc4\x85, do kt\xc3\xb3rej do\xc5\x82\xc4\x85czane s\xc4\x85 elementy listy. Je\xc5\xbceli w powy\xc5\xbcszym przyk\xc5\x82adzie jako warto\xc5\x9b\xc4\x87 pocz\xc4\x85tkow\xc4\x85 ustawiono by liczb\xc4\x99 0, foldr wykona\xc5\x82by dzia\xc5\x82ania zgodnie z notacj\xc4\x85 1 + (2 + (3 + (4 + (5 + 0)))), za\xc5\x9b foldl: ((((0 + 1) + 2) + 3) + 4) + 5.\n_START_SECTION_\nZwijanie list jako operacja strukturalna\n_START_PARAGRAPH_\nJak ju\xc5\xbc by\xc5\x82o wspomniane, funkcje fold mog\xc4\x85 dzia\xc5\x82a\xc4\x87 na zasadzie przypominaj\xc4\x85cej zamian\xc4\x99 przecink\xc3\xb3w na operatory. W rzeczywisto\xc5\x9bci jest to bli\xc5\xbcsze zamianie komponent\xc3\xb3w tworz\xc4\x85cych struktur\xc4\x99 funkcjami i warto\xc5\x9bciami, post\xc4\x99puj\xc4\x85c w uporz\xc4\x85dkowany odg\xc3\xb3rnie spos\xc3\xb3b._NEWLINE_W wi\xc4\x99kszo\xc5\x9bci j\xc4\x99zyk\xc3\xb3w programowania lista jest albo list\xc4\x85 pust\xc4\x85 (w informatyce najcz\xc4\x99\xc5\x9bciej oznaczan\xc4\x85 przez nil), b\xc4\x85d\xc5\xba te\xc5\xbc jest to wynik do\xc5\x82\xc4\x85czenia pewnego elementu do ko\xc5\x84ca istniej\xc4\x85cej listy (oznaczane zwykle jako cons). W j\xc4\x99zyku Haskell lista pusta oznaczana jest jako [], za\xc5\x9b operacja cons oznaczana jest symbolem (:) (dwukropek). W takim zapisie lista [1,2,3,4,5] ma posta\xc4\x87: 1:2:3:4:5:[]. W\xc3\xb3wczas mo\xc5\xbcna spojrze\xc4\x87 na funkcj\xc4\x99 foldr jako form\xc4\x99 "zamiany" nil na ko\xc5\x84cu listy warto\xc5\x9bci\xc4\x85 pocz\xc4\x85tkow\xc4\x85, za\xc5\x9b operacji cons - konkretn\xc4\x85 funkcj\xc4\x85. Najpro\xc5\x9bciej ilustruje to poni\xc5\xbcszy diagram:_NEWLINE_Dla foldl warto\xc5\x9b\xc4\x87 pocz\xc4\x85tkowa zast\xc4\x85pi\xc5\x82aby nil umieszczony na pocz\xc4\x85tku listy, co prezentuje kolejny diagram:_NEWLINE_Diagramy te ilustruj\xc4\x85 r\xc3\xb3wnie\xc5\xbc pochodzenie s\xc5\x82\xc3\xb3w "lewy" i "prawy" fold. Mo\xc5\xbcna r\xc3\xb3wnie\xc5\xbc zaobserwowa\xc4\x87, \xc5\xbce wywo\xc5\x82anie foldr (:) [] to funkcja identyczno\xc5\x9bciowa na li\xc5\x9bcie, ka\xc5\xbcda lista przekazana jako parametr do tego wywo\xc5\x82ania, zostanie zwr\xc3\xb3cona jako wynik w niezmienionym kszta\xc5\x82cie.\n_START_SECTION_\nKolejno\xc5\x9b\xc4\x87 ewaluacji\n_START_PARAGRAPH_\nJe\xc5\xbceli w j\xc4\x99zyku wyst\xc4\x99puje leniwa ewaluacja, foldr od razu zwr\xc3\xb3ci wynik wywo\xc5\x82ania funkcji f na rekurencyjnym wo\xc5\x82aniu foldr. Przy czym je\xc5\xbceli f mo\xc5\xbce obliczy\xc4\x87 wynik nie korzystaj\xc4\x85c z wyniku wewn\xc4\x99trznej rekurencji, nie b\xc4\x99dzie ona przetwarzana i rekurencja og\xc3\xb3lna ulegnie zatrzymaniu. Z tego powodu foldr mo\xc5\xbcna wywo\xc5\x82ywa\xc4\x87 na niesko\xc5\x84czonych listach. Z drugiej strony foldl na listach niesko\xc5\x84czonych uleg\xc5\x82by zap\xc4\x99tleniu._NEWLINE_Kolejn\xc4\x85 kwesti\xc4\x85, kt\xc3\xb3ra pojawia si\xc4\x99 przy leniwej ewaluacji lewych fold\xc3\xb3w, jest to, \xc5\xbce warto\xc5\x9b\xc4\x87 pocz\xc4\x85tkowa nie jest obliczana, zanim nie zostanie wywo\xc5\x82ana rekurencja. Mo\xc5\xbce to doprowadzi\xc4\x87 do przepe\xc5\x82nienia stosu, je\xc5\xbceli po przejrzeniu d\xc5\x82ugiej listy trzeba jeszcze obliczy\xc4\x87 wielkie wyra\xc5\xbcenie. Z tego powodu niekt\xc3\xb3re j\xc4\x99zyki wprowadzaj\xc4\x85 ograniczenia na foldl wymuszaj\xc4\x85ce ewaluacj\xc4\x99 warto\xc5\x9bci pocz\xc4\x85tkowej przed przyst\xc4\x85pieniem do rekurencji. W j\xc4\x99zyku Haskell tak\xc4\x85 funkcjonalno\xc5\x9b\xc4\x87 realizuje foldl\' (gdzie apostrof oznacza prime) dost\xc4\x99pna w bibliotece Data.List_NEWLINE_W sytuacji, gdy nie znamy elementu neutralnego funkcji f, b\xc4\x85d\xc5\xba chcemy aby operacja wykonywana by\xc5\x82a jedynie na elementach zadanej listy, bez dodatkowej warto\xc5\x9bci pocz\xc4\x85tkowej, w\xc3\xb3wczas mamy do dyspozycji odmiany foldr i foldl. Foldr1 i foldl1 u\xc5\xbcywaj\xc4\x85 odpowiednio ostatniego i pierwszego elementu listy w miejsce warto\xc5\x9bci pocz\xc4\x85tkowej. 1 w nazwie odnosi si\xc4\x99 m.in. do minimalnej wielko\xc5\x9bci listy (przynajmniej 1 element).\n_START_SECTION_\nPrzyk\xc5\x82ady\n_START_PARAGRAPH_\nOdwr\xc3\xb3cenie listy:_NEWLINE_rev = foldl (\\ys x -> x : ys) [] -- Haskell_NEWLINE_(reduce (fn [ys x] (cons x ys)) () coll) ; Clojure_NEWLINE_gdzie (\\ys x -> x : ys) i (fn [ys x] (cons x ys)) to funkcje, kt\xc3\xb3re zwracaj\xc4\x85 list\xc4\x99 ys z elementem x na pocz\xc4\x85tku._NEWLINE_Funkcja wy\xc5\xbcszego rz\xc4\x99du map:_NEWLINE_map f = foldr ((:) . f) [] -- Haskell_NEWLINE_(defn map [f coll] (reduce _NEWLINE_    (fn [ys x] (cons (f x) ys)) () (reverse coll))) ; Clojure_NEWLINE_gdzie kropka (.) to operator sk\xc5\x82adania funkcji, a dwukropek (:) to tworzenie listy (cons). Clojure nie posiada funkcji reduce-right/foldr, ale wywo\xc5\x82anie reverse przynosi ten sam efekt. _NEWLINE_Z\xc5\x82\xc4\x85czenie napis\xc3\xb3w aby uzyska\xc4\x87: "(f 1 (f 2 (f 3 (f 4 (f 5 z)))))"_NEWLINE_foldr (\\x y -> concat ["(f ",x," ",y,")"]) "z" ["1","2","3","4","5"]_NEWLINE_Z\xc5\x82\xc4\x85czenie napis\xc3\xb3w aby uzyska\xc4\x87: "(f (f (f (f (f z 1) 2) 3) 4) 5)"_NEWLINE_foldl (\\x y -> concat ["(f ",x," ",y,")"]) "z" ["1","2","3","4","5"]'