Shrnutí seznamu

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 29. května 2021; ověření vyžaduje 1 úpravu .

Skládání seznamu ( anglicky  folding , také známé jako snížit , akumulovat ) v programování  je funkce vyššího řádu , která pomocí dané funkce převádí datovou strukturu na jednu atomickou hodnotu. Operace skládání se často používá ve funkčním programování při zpracování seznamů . Skládání lze zobecnit na libovolný algebraický datový typ pomocí pojmu katamorfismus z teorie kategorií .

Souhrnná funkce má obvykle tři argumenty: kombinační funkci f, počáteční hodnotu starta datovou strukturu seq(seznam v nejjednodušší podobě). V závislosti na vlastnostech kombinační funkce mohou existovat různé implementace a různé strategie výpočtu . Někdy kumulativní funkce nepřebírá počáteční hodnotu, ale vyžaduje neprázdný seznam; ale v mnoha případech může být žádoucí zadat nenulovou počáteční hodnotu, která bude použita při prvním použití kombinační funkce. Použití počáteční hodnoty je nutné, když se typ výsledku kombinační funkce liší od typu prvků seznamu, v takovém případě musí být počáteční hodnota stejného typu jako typ výsledku.

Asociativita

U skládání pomocí asociativní operace nemá pořadí výpočtu vliv na výsledek, například výpočet součtu čísel seznamu (1 2 3 4 5), tedy jeho skládání součtem, lze provést v libovolném pořadí: nebo nebo , což umožňuje můžete vypočítat skládání různých částí seznamu současně, to znamená paralelizovat skládání kalkulačního seznamu ve víceprocesorových a clusterových systémech.

U neasociativních operací záleží na pořadí, proto je v obecném případě u skládání nutné specifikovat pořadí výpočtů, v souvislosti s tím skládání pravostranné ( pravoasociativní ) a skládání vlevo ( se rozlišují levé - asociativní ). Například pro seznam seq := (elem_1 elem_2 ... elem_n)vyhodnotí funkce levého asociativního skládání hodnotu výrazu:

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

a pravý asociativní:

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

Příklady

Faktoriál n lze reprezentovat jako seznam čísel od 2 do n složený pomocí operace násobení (například v jazyce Haskell ):

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

Tady:

fac - deklarace faktoriálové funkce
n - vstupní parametr
za znaménkem =(rovná se) následuje definice funkce
foldl - konvoluční funkce
1 — počáteční hodnota pro konvoluci
[2..n] - je určen seznam, podle kterého se má složit - čísla od 2 do n

Příklad podobné funkce v Scala :

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

Literatura