Lista összesítés

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. május 29-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A programozásban  a listahajtogatás ( angol  folding , más néven redukálni , felhalmozni ) egy magasabb rendű függvény , amely egy adott függvény segítségével egyetlen atomi értékké alakítja át az adatstruktúrát . A fold műveletet gyakran használják a funkcionális programozásban listák feldolgozásakor . A hajtogatás általánosítható tetszőleges algebrai adattípusra a katamorfizmus fogalmával a kategóriaelméletből .

Az összesítő függvény általában három argumentumot tartalmaz: egy kombináló függvényt f, egy kezdőértéket startés egy adatstruktúrát seq(a legegyszerűbb formában egy lista). A kombináló függvény tulajdonságaitól függően különböző megvalósítások és különböző számítási stratégiák létezhetnek . Néha az összesítő függvény nem vesz fel kezdeti értéket, de nem üres listát igényel; de sok esetben kívánatos lehet egy nullától eltérő kezdőérték megadása, amelyet a kombináló függvény első alkalmazásakor használunk. Kezdőérték használatára akkor van szükség, ha az egyesítő függvény eredménytípusa eltér a listaelemek típusától, ebben az esetben a kezdőértéknek azonos típusúnak kell lennie az eredménytípussal.

Aszociativitás

Asszociatív művelettel történő hajtogatás esetén a számítási sorrend nem befolyásolja az eredményt, például a lista számainak összegének kiszámítása (1 2 3 4 5), vagyis az összeggel való hajtása tetszőleges sorrendben elvégezhető: vagy vagy , amely lehetővé teszi a lista különböző részeinek egyidejű hajtogatását számolja ki, azaz párhuzamosítsa a számítási lista hajtogatását többprocesszoros és fürt rendszerekben.

A nem asszociatív műveleteknél a sorrend számít, ezért általában a hajtogatáshoz szükséges a számítások sorrendjének megadása, ehhez kapcsolódóan a jobb oldali hajtás ( jobbra asszociatív ) és a bal oldali hajtás ( bal -asszociatív ) különböztetjük meg. Például egy lista seq := (elem_1 elem_2 ... elem_n)esetén a bal oldali asszociatív hajtás függvény a kifejezés értékét értékeli:

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

és jobb asszociatív:

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

Példák

Az n faktoriális ábrázolható 2 és n közötti számok listájaként, a szorzási művelettel hajtva (például Haskell nyelven ):

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

Itt:

fac - a faktoriális függvény deklarálása
n - bemeneti paraméter
az előjel =(egyenlő) után következik a függvény meghatározása
foldl - konvolúciós függvény
1 — a konvolúció kezdeti értéke
[2..n] - egy lista van megadva, amely alapján hajtogatható - számok 2 -től n -ig

Példa egy hasonló funkcióra a Scalában :

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

Irodalom