Seznam rozdílů - Difference list

v počítačová věda, termín seznam rozdílů může odkazovat na jednu ze dvou datové struktury pro reprezentaci předpon seznamy. Jedna z těchto datových struktur obsahuje dva seznamy a představuje rozdíl těchto dvou seznamů. To se běžně používá v logickém programovacím jazyce Prolog. Druhá datová struktura je a funkční reprezentace seznamu s efektivní zřetězení úkon. Ve druhém přístupu jsou seznamy rozdílů implementovány jako jeden argument funkce, které berou seznam jako argument a připojit se k tomuto seznamu. V důsledku toho je zřetězení seznamů rozdílů druhého typu implementováno v podstatě jako složení funkce, který je O (1). Seznam však samozřejmě musí být nakonec vytvořen (za předpokladu, že jsou potřebné všechny jeho prvky), což je zjevně alespoň O (n).

Rozdílové seznamy jako funkce

Seznam rozdílů druhého řazení představuje seznamy jako funkce F, který po zadání seznamu X, vrátí seznam, který F představuje, předřazeno X. Obvykle se používá ve funkčních programovacích jazycích, jako je Haskell, ačkoli to mohlo být použito také v imperativních jazycích. Zda je tento druh rozdílového seznamu efektivnější než jiné reprezentace seznamu, závisí na vzorcích použití. Pokud algoritmus vytvoří seznam zřetězením menších seznamů, které jsou samy vytvářeny zřetězením stále menších seznamů, pak použití seznamů rozdílů může zlepšit výkon efektivním "sloučením" výpočtů sestavování seznamu.

Jako funkce jsou seznamy rozdílů Cayleyovou reprezentací seznamů jako monoidů, konkrétněji jejich transformační monoid indukované množením vlevo.

Příklady použití jsou v ShowS napište do Preludia Haskell a do Donald Bruce Stewart knihovna seznamů rozdílů pro Haskell.

externí odkazy