Seznam objektů - List object

v teorie kategorií, abstraktní odvětví matematika a ve svých aplikacích pro logika a teoretická informatika, a objekt seznamu je abstraktní definice a seznam, tj konečný objednal sekvence.

Formální definice

Nechat C být kategorie s konečnou produkty a a koncový objekt 1. A objekt seznamu přes objekt A z C je:

  1. objekt LA,
  2. A morfismus ÓA : 1 → LA, a
  3. morfismus sA : A × LALA

takový, že pro jakýkoli objekt B z C s mapami b : 1 → B a t : A × BBexistuje jedinečný F : LAB tak, že následující diagram dojíždí:

Komutativní diagram vyjadřující rovnice v definici objektu seznamu

kde 〈idA, F〉 Označuje šipku vyvolanou univerzální vlastnictví produktu při použití na idA (totožnost na A) a F. Zápis A* (à la Kleene hvězda ) se někdy používá k označení seznamů A.[1]

Ekvivalentní definice

V kategorii s koncovým objektem 1, binární koprodukty (označeno +) a binární produkty (označené ×), objekt seznamu A lze definovat jako počáteční algebra z endofunctor který působí na objekty X ↦ 1 + (A × X) a na šipkách pomocí F ↦ [id1, 〈IdA, F〉].[2]

Příklady

  • v Soubor, kategorie sad, seznam objektů přes sadu A jsou jednoduše konečné seznamy s elementy vybrané z A. V tomto případě, ÓA vybere prázdný seznam a sA odpovídá přidání prvku do záhlaví seznamu.
  • V počet indukčních konstrukcí nebo podobné teorie teorií s indukčními typy (nebo heuristicky, dokonce silně napsaný funkční jazyky jako Haskell ), seznamy jsou typy definované dvěma konstruktory, nula a nevýhody, které odpovídají ÓA a sA, resp. Princip rekurze seznamů zaručuje, že mají očekávanou univerzální vlastnost.

Vlastnosti

Stejně jako všechny konstrukce definované a univerzální vlastnictví, seznamy nad objektem jsou jedinečné až kanonický izomorfismus.

Objekt L1 (seznamy přes objekt terminálu) má univerzální vlastnost a přirozené číslo objektu. V jakékoli kategorii se seznamy lze definovat délka seznamu LA být jedinečným morfismem l : LAL1 což umožňuje následující diagram dojíždět:[3]

Komutativní diagram vyjadřující rovnice v definici délky objektu seznamu

Reference

  1. ^ Johnstone 2002, A2.5.15.
  2. ^ Philip Wadler: Rekurzivní typy zdarma! University of Glasgow, červenec 1998. Koncept.
  3. ^ Johnstone 2002, str. 117.
  • Johnstone, Peter T. (2002). Náčrtky slona: souhrn teorie topos. Oxford: Oxford University Press. ISBN  0198534256. OCLC  50164783.

Viz také