Kontejner (teorie typů) - Container (type theory)

v teorie typů, kontejnery jsou abstrakce, které umožňují různé "typy sběru", jako např seznamy a stromy, být reprezentován jednotným způsobem. A (unární ) kontejner je definován typem tvary S a typová rodina pozic P, indexováno S. The rozšíření kontejneru je rodina závislých párů skládající se z tvaru (typu S) a funkce z pozic tohoto tvaru do typu prvku. Na kontejnery lze pohlížet jako kanonické formy pro typy sbírek.^[1]

U seznamů je typem tvaru přirozená čísla (včetně nuly). Odpovídající typy pozic jsou typy přirozených čísel menší než tvar pro každý tvar.

U stromů je typem tvaru typ stromů jednotek (tj. Stromy bez informací, pouze struktura). Odpovídající typy pozic jsou pro každý tvar izomorfní s typy platných cest od kořene k určitým uzlům ve tvaru.

Všimněte si, že přirozená čísla jsou izomorfní se seznamy jednotek. Obecně bude typ tvaru vždy izomorfní k původní rodině generických typů kontejnerů (seznam, strom atd.) Aplikovaných na jednotku.

Jednou z hlavních motivací pro zavedení pojmu kontejnery je podpora generické programování v závisle napsané nastavení.^[1]

Kategorické aspekty

Rozšíření kontejneru je endofunctor. Trvá to funkci G na

${ Displaystyle lambda left (s, f right). left (s, g circ f right)}$

To odpovídá známému mapa g v případě seznamů a dělá něco podobného pro jiné kontejnery.

Indexované kontejnery

Indexované kontejnery (také známý jako závislé polynomiální funktory) jsou zobecněním kontejnerů, které mohou představovat širší třídu typů, jako jsou vektory (velké seznamy).^[2]

Typ prvku (nazývaný Typ vstupu) je indexován podle tvaru a polohy, takže se může lišit podle tvaru a polohy a rozšíření (tzv typ výstupu) je také indexován podle tvaru.

Viz také

Reference

^ ^A ^b Michael Abbott; Thorsten Altenkirch; Neil Ghani (2005). "Kontejnery: Konstrukce přísně pozitivních typů". Teoretická informatika. 342 (1): 3–27. doi:10.1016 / j.tcs.2005.06.002.
^ Thorsten Altenkirch, Neil Ghani, Peter Hancock, Conor McBride a Peter Morris. "Indexované kontejnery" (PDF). Nepublikovaný rukopis. Citováno 2008-10-30. Citovat deník vyžaduje | deník = (Pomoc)CS1 maint: více jmen: seznam autorů (odkaz)

externí odkazy

Typy kontejnerů blog

{ displaystyle Gamma vdash x: { text {Int}}}

Tento teorie programovacího jazyka nebo teorie typů související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.

[containers-1] A ^b Michael Abbott; Thorsten Altenkirch; Neil Ghani (2005). "Kontejnery: Konstrukce přísně pozitivních typů". Teoretická informatika. 342 (1): 3–27. doi:10.1016 / j.tcs.2005.06.002.

[indexed-containers-2] Thorsten Altenkirch, Neil Ghani, Peter Hancock, Conor McBride a Peter Morris. "Indexované kontejnery" (PDF). Nepublikovaný rukopis. Citováno 2008-10-30. Citovat deník vyžaduje | deník = (Pomoc)CS1 maint: více jmen: seznam autorů (odkaz)

[1]

[2]