Indukční typ - Inductive type - Wikipedia

v teorie typů, systém má indukční typy pokud má zařízení pro vytváření nového typu spolu s konstantami a funkcemi, které vytvářejí termíny tohoto typu. Funkce má podobnou roli datové struktury v programovacím jazyce a umožňuje teorii typů přidat pojmy jako čísla, vztahy, a stromy. Jak název napovídá, indukční typy mohou být samoreferenční, ale obvykle pouze způsobem, který to umožňuje strukturální rekurze.

Standardní příklad je kódování přirozená čísla použitím Peanovo kódování.

 Induktivní nat : Typ :=   | 0 : nat   | S : nat -> nat.

Zde se přirozené číslo vytvoří buď z konstanty "0", nebo použitím funkce "S" na jiné přirozené číslo. „S“ je nástupnická funkce což představuje přidání 1 k číslu. „0“ je tedy nula, „S 0“ je jedna, „S (S 0)“ je dvě, „S (S (S 0))“ je tři atd.

Od svého zavedení byly indukční typy rozšířeny tak, aby kódovaly stále více struktur, přičemž stále existují predikativní a podpora strukturální rekurze.

Odstranění

Induktivní typy obvykle přicházejí s funkcí prokazující jejich vlastnosti. „Nat“ tedy může přijít s:

 nat_elim : (pro všechny P : nat -> Podpěra, (P 0) -> (pro všechny n, P n -> P (S n)) -> (pro všechny n, P n)).

Toto je očekávaná funkce strukturální rekurze pro typ "nat".

Implementace

Typy W a M.

Typy W jsou opodstatněný typy v intuicionistická teorie typů (ITT).^[1] Zobecňují přirozená čísla, seznamy, binární stromy a další datové typy ve tvaru stromu. Nechat U být vesmír typů. Vzhledem k typu A : U a a závislá rodina B : A → U, lze vytvořit typ W. ${ displaystyle { mathsf {W}} _ {a: A} B (a)}$ . Typ A lze považovat za „štítky“ pro (potenciálně nekonečně mnoho) konstruktorů indukčního typu, které jsou definovány, zatímco B označuje (potenciálně nekonečný) arity každého konstruktéra. W-typy (resp. M-typy) lze také chápat jako fundované (resp. Neopodstatněné) stromy s uzly označenými prvky A : A a kde uzel označen A má B(A) - mnoho podstromů.^[2] Každý typ W je izomorfní s počáteční algebrou tzv polynomiální funktor.

Nechat 0, 1, 2atd. být konečné typy s obyvateli 1₁ : 1, 1₂, 2₂:2Přirozená čísla lze definovat jako typ W.

{ displaystyle mathbb {N}: = { mathsf {W}} _ {x: mathbf {2}} f (x)}

s F : 2 → U je definováno F(1₂) = 0 (představující konstruktor pro nulu, který nepřijímá žádné argumenty) a F(2₂) = 1 (představující nástupnickou funkci, která vyžaduje jeden argument).

Lze definovat seznamy nad typem A : U tak jako ${ displaystyle operatorname {List} (A): = { mathsf {W}} _ {(x: mathbf {1} + A)} f (x)}$ kde

{ displaystyle { begin {aligned} f ( operatorname {inl} (1 _ { mathbf {1}})) & = mathbf {0} f ( operatorname {inr} (a)) & = mathbf {1} end {aligned}}}

a 1₁ je jediným obyvatelem města 1. Hodnota ${ displaystyle f ( operatorname {inl} (1 _ { mathbf {1}}))}$ odpovídá konstruktoru pro prázdný seznam, zatímco hodnota ${ displaystyle f ( operatorname {inr} (a))}$ odpovídá konstruktoru, který se připojí A na začátek jiného seznamu.

Konstruktor pro prvky obecného typu W. ${ displaystyle { mathsf {W}} _ {x: A} B (x)}$ má typ

{ displaystyle { mathsf {sup}}: prod _ {a: A} { Big (} B (a) až { mathsf {W}} _ {x: A} B (x) { Big )} to { mathsf {W}} _ {x: A} B (x).}

Toto pravidlo můžeme také napsat ve stylu a přirozený odpočet důkaz,

{ displaystyle { frac {a: A qquad f: B (a) až { mathsf {W}} _ {x: A} B (x)} {{ mathsf {sup}} (a, f ): { mathsf {W}} _ {x: A} B (x)}}.}

Pravidlo eliminace pro typy W funguje podobně jako strukturální indukce na stromech. Pokud kdykoli nemovitost (pod propozice jako typy výklad) ${ displaystyle C: { mathsf {W}} _ {x: A} B (x) do U}$ platí pro všechny podstromy daného stromu, platí také pro tento strom, pak platí pro všechny stromy.

{ displaystyle { frac {w: { mathsf {W}} _ {a: A} B (a) qquad a: A, ; f: B (a) na { mathsf {W}} _ {x: A} B (x), ; c: prod _ {b: B (a)} C (f (b)) ; vdash ; h (a, f, c): C ({ mathsf {sup}} (a, f))} {{ mathsf {elim}} (w, h): C (w)}}}

V teoriích typu rozšíření lze definovat typy W (resp. Typy M) až izomorfismus tak jako počáteční algebry (resp. konečné uhlí) pro polynomiální funktory. V tomto případě vlastnost iniciálnosti (res. Konečnost) odpovídá přímo příslušnému indukčnímu principu.^[3] V teoriích intenzionálního typu s axiom univalence, tato korespondence platí až do homotopy (výroková rovnost).^[4]^[5]^[6]

M-typy jsou dvojí na typy W, představují koinduktivní (potenciálně nekonečná) data jako proudy.^[7] M-typy lze odvodit z W-typů.^[8]

Vzájemně induktivní definice

Tato technika umožňuje nějaký definice více typů, které na sobě závisí. Například definování dvou parita predikuje na přirozená čísla pomocí dvou vzájemně indukčních typů v Coq:

Induktivní dokonce : nat -> Podpěra :=  | zero_is_even : dokonce Ó  | S_of_odd_is_even : (pro všechny n:nat, zvláštní n -> dokonce (S n))s zvláštní : nat -> Podpěra :=  | S_of_even_is_odd : (pro všechny n:nat, dokonce n -> zvláštní (S n)).

Indukční rekurze

Indukční rekurze začala jako studie limitů ITT. Jakmile byly limity nalezeny, změnily se na pravidla, která umožňovala definovat nové indukční typy. Tyto typy mohly záviset na funkci a funkci na typu, pokud byly oba definovány současně.

Typy vesmíru lze definovat pomocí indukční rekurze.

Indukce-indukce

Indukce-indukce umožňuje definici typu a rodiny typů současně. Takže typ $A$ a rodina typů ${ displaystyle B: A psát}$ .

Vyšší indukční typy

Toto je aktuální oblast výzkumu v Teorie typu homotopy (HoTT). HoTT se liší od ITT podle typu identity (rovnosti). Vyšší indukční typy nejen definují nový typ s konstantami a funkcemi, které vytvářejí prvky typu, ale také nové instance typu identity, které se jich týkají.

Jednoduchým příkladem je $kruh$ typ, který je definován dvěma konstruktory, základním bodem;

základna : kruh

a smyčka;

smyčka : základna = základna .

Existence nového konstruktoru pro typ identity umožňuje $kruh$ vyšší indukční typ.

Viz také

Koindukce umožňuje (účinně) nekonečné struktury v teorii typů.

Reference

^ Martin-Löf, Per (1984). Intuicionistická teorie typů (PDF). Sambin, Giovanni. Napoli: Bibliopolis. ISBN 8870881059. OCLC 12731401.
^ Ahrens, Benedikt; Capriotti, Paolo; Spadotti, Régis (12.04.2015). "Nepodložené stromy v teorii typu Homotopy". arXiv:1504.02949. doi:10.4230 / LIPIcs.TLCA.2015.17. Citovat deník vyžaduje | deník = (Pomoc)
^ Dybjer, Peter (1997). „Reprezentace indukčně definovaných množin pomocí wellorderings v teorii typů Martin-Löfa“. Teoretická informatika. 176 (1–2): 329–335. doi:10.1016 / s0304-3975 (96) 00145-4.
^ Awodey, Steve; Gambino, Nicola; Sojakova, Kristina (18.01.2012). "Induktivní typy v teorii homotopických typů". arXiv:1201.3898 [matematika.LO ].
^ Ahrens, Benedikt; Capriotti, Paolo; Spadotti, Régis (12.04.2015). „Nepodložené stromy v teorii typu Homotopy“. arXiv:1504.02949. doi:10.4230 / LIPIcs.TLCA.2015.17. Citovat deník vyžaduje | deník = (Pomoc)
^ Awodey, Steve; Gambino, Nicola; Sojakova, Kristina (2015-04-21). "Homotopy-počáteční algebry v teorii typů". arXiv:1504.05531 [matematika.LO ].
^ van den Berg, Benno; Marchi, Federico De (2007). "Nepodložené stromy v kategoriích". Annals of Pure and Applied Logic. 146 (1): 40–59. arXiv:matematika / 0409158. doi:10.1016 / j.apal.2006.12.001.
^ Abbott, Michael; Altenkirch, Thorsten; Ghani, Neil (2005). "Kontejnery: Konstrukce přísně pozitivních typů". Teoretická informatika. 342 (1): 3–27. doi:10.1016 / j.tcs.2005.06.002.

Program Univalent Foundations (2013). Teorie typu homotopy: Univalentní základy matematiky. Institut pro pokročilé studium.

externí odkazy

[1] Martin-Löf, Per (1984). Intuicionistická teorie typů (PDF). Sambin, Giovanni. Napoli: Bibliopolis. ISBN 8870881059. OCLC 12731401.

[2] Ahrens, Benedikt; Capriotti, Paolo; Spadotti, Régis (12.04.2015). "Nepodložené stromy v teorii typu Homotopy". arXiv:1504.02949. doi:10.4230 / LIPIcs.TLCA.2015.17. Citovat deník vyžaduje | deník = (Pomoc)

[3] Dybjer, Peter (1997). „Reprezentace indukčně definovaných množin pomocí wellorderings v teorii typů Martin-Löfa“. Teoretická informatika. 176 (1–2): 329–335. doi:10.1016 / s0304-3975 (96) 00145-4.

[4] Awodey, Steve; Gambino, Nicola; Sojakova, Kristina (18.01.2012). "Induktivní typy v teorii homotopických typů". arXiv:1201.3898 [matematika.LO ].

[5] Ahrens, Benedikt; Capriotti, Paolo; Spadotti, Régis (12.04.2015). „Nepodložené stromy v teorii typu Homotopy“. arXiv:1504.02949. doi:10.4230 / LIPIcs.TLCA.2015.17. Citovat deník vyžaduje | deník = (Pomoc)

[6] Awodey, Steve; Gambino, Nicola; Sojakova, Kristina (2015-04-21). "Homotopy-počáteční algebry v teorii typů". arXiv:1504.05531 [matematika.LO ].

[7] van den Berg, Benno; Marchi, Federico De (2007). "Nepodložené stromy v kategoriích". Annals of Pure and Applied Logic. 146 (1): 40–59. arXiv:matematika / 0409158. doi:10.1016 / j.apal.2006.12.001.

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]