Listă acumulare

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 29 mai 2021; verificarea necesită 1 editare .

Folding listă ( în engleză  pliere , cunoscută și sub numele de reducere , acumulare ) în programare  este o funcție de ordin superior care convertește o structură de date într-o singură valoare atomică folosind o funcție dată. Operația de pliere este adesea folosită în programarea funcțională la procesarea listelor . Plierea poate fi generalizată la un tip de date algebric arbitrar folosind noțiunea de catamorfism din teoria categoriilor .

O funcție de acumulare are de obicei trei argumente: o funcție de combinare f, o valoare inițială startși o structură de date seq(o listă, în cea mai simplă formă). În funcție de proprietățile funcției de combinare, pot exista diferite implementări și diferite strategii de calcul . Uneori, funcția de acumulare nu ia o valoare inițială, dar necesită o listă nevide; dar în multe cazuri poate fi de dorit să se specifice o valoare inițială diferită de zero, care va fi utilizată prima dată când se aplică funcția de combinare. Utilizarea unei valori inițiale este necesară atunci când tipul de rezultat al funcției de combinare este diferit de tipul elementelor listei, caz în care valoarea inițială trebuie să fie de același tip cu tipul de rezultat.

Asociativitate

Pentru plierea printr -o operație asociativă , ordinea de calcul nu afectează rezultatul, de exemplu, calcularea sumei numerelor listei (1 2 3 4 5), adică plierea acesteia după sumă, se poate face în orice ordine: sau sau , ceea ce permite tu să calculezi plierea diferitelor părți ale listei în același timp, adică să paralelizezi plierea listei de calcul în sistemele multiprocesor și cluster.

Pentru operațiile neasociative, ordinea contează, prin urmare, în cazul general, pentru pliere, se cere să se precizeze ordinea calculelor, în legătură cu aceasta, plierea la dreapta ( asociativa dreapta ) și la plierea la stânga ( stânga -asociativ ) se disting. De exemplu, pentru o listă seq := (elem_1 elem_2 ... elem_n), funcția de pliere asociativă din stânga va evalua valoarea expresiei:

(f ... (f (f start elem_1) elem_2) ... elem_n)

și asociativ drept:

(f elem_1 (f elem_2 ... (f elem_n start) ... )).

Exemple

Factorialul n poate fi reprezentat ca o listă de numere de la 2 la n pliate folosind operația de înmulțire (de exemplu, în limbajul Haskell ):

fac n = foldl ( * ) 1 [ 2 .. n ]

Aici:

fac - declararea funcţiei factoriale
n - parametru de intrare
după semn =(egal) vine definiția funcției
foldl - functia de convolutie
1 — valoarea inițială pentru convoluție
[2..n] - este specificată o listă prin care să se plieze - numere de la 2 la n

Un exemplu de funcție similară în Scala :

def fac ( n : BigInt ) = ( BigInt ( 2 ) to n ). foldLeft ( BigInt ( 1 ))( _ * _ )

Literatură