Fold (funcție de ordin înalt)

În programarea funcțională, fold sau reduce sau accumulate este o familie de funcții de ordin înalt care procesează o structură de date într-o anumită ordine și construiește o valoare de returnat. Aceasta este opusă familiei de funcții unfold care primesc o valoare de start și aplică o funcție asupra ei pentru a genera o structură de date. De obicei, o funcție fold este formată din două entități: o funcție de combinare și o structură de date, de obicei o listă de elemente. Astfel, funcția combină elementele structurii de date într-un anumit mod sistematic.

Exemplu

Aplicarea funcției fold asupra listei [1,2,3,4,5] cu operatorul de adunare rezultă în 15, suma elementelor listei [1,2,3,4,5]. Ca idee, se poate imagina că se înlocuiesc virgulele din listă cu operatorul +, rezultând 1+2+3+4+5.

În exemplul de mai sus, + este o operație asociativă, deci modul de așezare a parantezelor este irelevant. În cazul general, pentru funcții binare neasociative, ordinea în care elementele sunt combinate contează. Asupra listelor, există două posibilități: ori prin combinarea recursivă a primului element cu rezultatul restului elementelor (operație numită right fold - fold la dreapta), ori prin combinarea recursivă a rezultatelor primelor elemente cu ultimul (operație numită left fold - fold la stânga). În primul caz, suma ar avea parantezele 1 + (2 + (3 + (4 + 5))), pe când, în al doilea caz, parantezele ar fi (((1 + 2) + 3) + 4) + 5.

În practică, este natural și convenient să existe o valoare inițială care, în cazul operației la dreapta, să fie folosită când se ajunge la sfârșitul listei, iar, în cazul operației la stânga, să fie combinată cu primul element din listă. În exemplul de mai sus, valoarea 0 este cea aleasă ca valoare inițială, formând 1 + (2 + (3 + (4 + (5 + 0)))) pentru recursia la dreapta, și ((((0 + 1) + 2) + 3) + 4) + 5 pentru recursia la stânga.