Počáteční algebra - Initial algebra
![]() | tento článek potřebuje další citace pro ověření.Prosinec 2017) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
Definice
v matematika, an počáteční algebra je počáteční objekt v kategorie z -algebry za dané endofunctor . Tato iniciálnost poskytuje obecný rámec pro indukce a rekurze.
Příklady
Funktor
Zvažte endofunctor odesílání na , kde je jednobodový (jedináček ) soubor, koncový objekt v kategorii. Algebra pro tento endofunktor je množina (volal dopravce algebry) společně s a funkce . Definování takové funkce se rovná definování bodu a funkce .Definovat
a
Pak sada přirozených čísel spolu s funkcí je iniciála -algebra. Iniciálnost ( univerzální vlastnictví pro tento případ) není těžké stanovit; unikátní homomorfismus libovolně -algebra , pro prvek a funkce zapnuta , je funkce odesílající přirozené číslo na , to znamená, , - složená aplikace na .
Sada přirozená čísla je nositel počáteční algebry pro tento funktor: bod je nula a funkce je nástupnická funkce.
Funktor
U druhého příkladu zvažte endofunctor na kategorii souprav, kde je množina přirozených čísel. Algebra pro tento endofunktor je množina spolu s funkcí . K definování takové funkce potřebujeme bod a funkce . Sada konečných seznamy přirozených čísel je počáteční algebra pro tento funktor. Jedná se o prázdný seznam a funkci nevýhody, vezmeme číslo a konečný seznam a vrátíme nový konečný seznam s číslem v čele.
V kategoriích s binárními koprodukty, právě uvedené definice jsou ekvivalentní obvyklým definicím a přirozené číslo objektu a a objekt seznamu, resp.
Závěrečná uhlí
Duálně, a závěrečná uhlí je koncový objekt v kategorii -coalgebry. Konečnost poskytuje obecný rámec pro koindukce a korekční.
Například pomocí stejného funktor stejně jako dříve je uhelná brzda definována jako množina spolu s funkcí . Definování takové funkce se rovná definování a částečná funkce F': X ⇸ Y jehož doména je tvořen těmi pro který patří . Na takovou strukturu lze pohlížet jako na řetězec sad, na kterých není definováno, do kterých prvků se mapuje podle , do kterých prvků se mapuje podle atd. a obsahující zbývající prvky . S ohledem na to je sada skládající se z množiny přirozených čísel rozšířených o nový prvek je nositelem závěrečné uhlí v kategorii, kde je funkce předchůdce ( inverzní funkce nástupce) na pozitivní přirozené, ale chová se jako identita na novém prvku : , . Tato sada to je nositel konečné uhlígebry z je známá jako množina konaturálních čísel.
U druhého příkladu zvažte stejný funktor jako dříve. V tomto případě se nosič konečné uhelné mozku skládá ze všech seznamů přirozených čísel, konečných i nekonečný. Mezi operace patří testovací funkce testující, zda je seznam prázdný, a dekonstrukční funkce definovaná na neprázdných seznamech, která vrací dvojici skládající se z hlavy a ocasu vstupního seznamu.
Věty
- Počáteční algebry jsou minimální (tj. Nemají žádnou správnou subalgebru).
- Konečné uhlígebry jsou jednoduchý (tj. nemají žádné správné kvocienty).
Využití v informatice
Různé konečné datové struktury použito v programování, jako seznamy a stromy, lze získat jako počáteční algebry konkrétních endofunktorů. I když pro daný endofunktor může existovat několik počátečních algeber, jsou unikátní až do izomorfismus, což neformálně znamená, že „pozorovatelné“ vlastnosti datové struktury lze adekvátně zachytit definováním jako počáteční algebry.
Chcete-li získat typ seznamů, jejichž prvky jsou členy množiny , zvažte, že operace vytváření seznamů jsou:
V kombinaci do jedné funkce dávají:
- ,
což z toho dělá -algebra pro endofunctor odesílání na . Je to ve skutečnosti the počáteční -algebra. Iniciálnost je určena funkcí známou jako foldr v funkční programovací jazyky jako Haskell a ML.
Rovněž, binární stromy s prvky na listech lze získat jako počáteční algebru
- .
Typy získané tímto způsobem jsou známé jako algebraické datové typy.
Typy definované pomocí nejméně pevný bod konstrukce s funktorem lze považovat za iniciálu -algebra, za předpokladu, že parametricita drží pro typ.[1]
Dvojím způsobem existuje podobný vztah mezi pojmy největší pevný bod a terminál -coalgebra, s aplikacemi do koinduktivní typy. Ty lze použít k povolení potenciálně nekonečný předměty při údržbě silná normalizační vlastnost.[1] V silně normalizujícím (každý program končí) charitativním programovacím jazykem lze pro dosažení překvapivých výsledků použít koinduktivní datové typy, např. definování vzhlédnout konstrukty k implementaci takových "silný" funkce jako Ackermannova funkce.[2]
Viz také
Poznámky
- ^ A b Philip Wadler: Rekurzivní typy zdarma! University of Glasgow, červenec 1998. Koncept.
- ^ Robin Cockett: Charitable Thoughts (ps.gz )
externí odkazy
- Kategorické programování s indukčními a koindukčními typy od Varmo Vene
- Rekurzivní typy zdarma! Philip Wadler, University of Glasgow, 1990-2014.
- Počáteční algebra a závěrečná sémantika koalgebry pro souběžnost autor: J.J.M.M. Rutten a D. Turi
- Iniciálnost a konečnost od CLiki
- Zadaní koncoví tlumočníci bez značek Oleg Kiselyov