Algebra początkowa

W matematyce algebra początkowa jest obiektem początkowym w kategorii F $-$ algebr dla danego endofunktora $F$ . Ta inicjalność zapewnia ogólne ramy dla indukcji i rekurencji .

Przykłady

Funktor $1 + (-)$

Rozważmy endofunktor $F : Set \to Set$ wysyłający $X$ do $1 + X$ , gdzie $1 to$ zbiór jednopunktowy ( singleton ) , obiekt końcowy w kategorii. Algebrą dla tego endofunktora jest zbiór $X$ (nazywany nośnikiem algebry) wraz z funkcją $f : (1 + X) \to X$ . Zdefiniowanie takiej funkcji sprowadza się do zdefiniowania punktu ${\ Displaystyle x \ w X}$ i funkcja $X \to X$ . Definiować

{\ Displaystyle {\ rozpocząć {wyrównane} \ nazwa operatora {zero} \ dwukropek 1 i \ longrightarrow \ mathbf {N} \\ * & \ longmapsto 0 \ koniec {wyrównane}}}

I

{\ Displaystyle {\ rozpocząć {wyrównane} \ operatorname {succ} \ dwukropek \ mathbf {N} & \ longrightarrow \ mathbf {N} \\ n & \ longmapsto n + 1. \ koniec {wyrównany}}}

Wtedy zbiór $N$ liczb naturalnych wraz z funkcją $[zero,succ]: 1 + N \to N$ jest początkową $F$ -algebrą. Inicjalność ( właściwość uniwersalna w tym przypadku) nie jest trudna do ustalenia; unikalny homomorfizm do dowolnej $F$ -algebry $(A, [e, f])$ , dla $e : 1 \to A$ element $A$ i $f : A \to A$ funkcja na $A$ , to funkcja przesyłająca liczbę naturalną $n$ do $f n (e)$ , to znaczy $f (f (\dots(f (e))\dots))$ , $n$ -krotne zastosowanie $f$ do $e$ .

Zbiór liczb naturalnych jest nośnikiem algebry początkowej dla tego funktora: punktem jest zero, a funkcją jest następnik .

Funktor $1 + N \times (-)$

Jako drugi przykład rozważmy endofunktor $1 + N \times (-)$ w kategorii zbiorów, gdzie $N$ jest zbiorem liczb naturalnych. Algebrą dla tego endofunktora jest zbiór $X$ wraz z funkcją $1 + N \times X \to X$ . Aby zdefiniować $×$ $N, X \to .$ potrzebujemy i funkcji Zbiór list skończonych liczb naturalnych jest algebrą początkową tego funktora. Chodzi o pustą listę, a funkcją jest cons , biorąc liczbę i skończoną listę i zwracając nową skończoną listę z liczbą na początku.

W kategoriach z koproduktami binarnymi podane definicje są równoważne zwykłym definicjom odpowiednio obiektu liczby naturalnej i obiektu listy .

Końcowa koalgebra

Podwójnie końcowa koalgebra jest obiektem końcowym w kategorii $F$ -koalgebr . Ostateczność zapewnia ogólne ramy dla koindukcji i współkursowania .

Na przykład, używając tego samego funktora $1 + (-)$ jak poprzednio, kogebra jest zdefiniowana jako zbiór $X$ wraz z funkcją $f : X \to (1 + X)$ . Zdefiniowanie takiej funkcji sprowadza się do zdefiniowania funkcji częściowej $f ' : X ⇸ Y$ , której dziedzinę tworzą te , dla których $f (x)$ należy do $1$ ${\ displaystyle x \ in X}$ . Taką strukturę można postrzegać jako łańcuch zbiorów, w których $X 0$ nie jest zdefiniowane $f' ,$ $X 1$ , które elementy odwzorowują się w $X 0$ przez $f'$ , $X 2$ które elementy odwzorowują się w $X 1$ przez $f'$ itd. oraz $X ω$ zawierający pozostałe elementy $X$ . Mając to na uwadze, zestaw ${\ Displaystyle \ mathbf {N} \ kubek \ {\ omega \}}$ składający się ze zbioru liczb naturalnych rozszerzonego o nowy element $ω$ jest nośnikiem ostatecznej węgla w kategorii, gdzie jest funkcją poprzednika ( odwrotnością funkcji następcy) na dodatnich liczbach naturalnych, ${\ displaystyle f'}$ ale działa jak tożsamość na nowym elemencie $ω$ : $f (n + 1) = n$ , $f (ω) = ω$ . Ten zbiór ${\ Displaystyle \ mathbf {N} \ kubek \ {\ omega \}}$ , który jest nośnikiem końcowej kogebry $1 + (-),$ jest znany jako zbiór liczb współnaturalnych.

Jako drugi przykład rozważmy ten sam funktor $1 + N \times (-),$ co poprzednio. W tym przypadku nośnikiem ostatecznej kogebry są wszystkie listy liczb naturalnych, zarówno skończonych, jak i nieskończonych . Operacje to funkcja testująca sprawdzająca, czy lista jest pusta, oraz funkcja dekonstrukcji zdefiniowana na niepustych listach, zwracająca parę składającą się z początku i końca listy wejściowej.

Twierdzenia

Algebry początkowe są minimalne (tj. nie mają właściwej podalgebry).
Końcowe węglanie są proste (tj. nie mają odpowiednich ilorazów).

Zastosowanie w informatyce

Różne skończone struktury danych używane w programowaniu , takie jak listy i drzewa , można otrzymać jako algebry początkowe określonych endofunktorów. Chociaż dla danego endofunktora może istnieć kilka algebr początkowych, są one unikalne aż do izomorfizmu , co nieformalnie oznacza, że „obserwowalne” właściwości struktury danych można odpowiednio uchwycić, definiując ją jako algebrę początkową.

Aby uzyskać typ $List(A)$ list, których elementy należą do zbioru $A$ , należy wziąć pod uwagę, że operacje tworzące listy to:

${\ Displaystyle \ operatorname {zero} \ dwukropek 1 \ do \ operatorname {Lista} (A)}$
$\ Displaystyle \ operatorname {cons} \ dwukropek A \ razy \ operatorname {Lista} (A) \ do \ operatorname {Lista} (A)}$

Połączone w jedną funkcję dają:

${\ Displaystyle [\ operatorname {zero} \ operatorname {przeciw} ] \ dwukropek (1+A\times \mathrm {Lista} (A))\do \mathrm {Lista} (A)}$

co czyni to $F$ -algebrą dla endofunktora $F$ wysyłającego $X$ do $1 + (A \times X)$ . W rzeczywistości jest to początkowa $F -$ algebra . Inicjalność jest ustalana przez funkcję znaną jako foldr w funkcjonalnych językach programowania, takich jak Haskell i ML .

Podobnie drzewa binarne z elementami na liściach można otrzymać jako algebrę początkową

${\ Displaystyle [\ operatorname {wskazówka}, \ operatorname {dołącz} ] \ okrężnica A + (\ operatorname {drzewo} (A) \ razy \ operatorname {drzewo} (A)} \ do \ operatorname {drzewo} (A). }$

Otrzymane w ten sposób typy są znane jako algebraiczne typy danych .

Typy zdefiniowane za pomocą konstrukcji najmniejszego punktu stałego z funktorem $F$ można uważać za początkową $F$ -algebrę, pod warunkiem, że dla typu obowiązuje parametryczność .

W dwojaki sposób podobny związek istnieje między pojęciami największego punktu stałego i końcowej $F$ -koalgebry, z zastosowaniami do typów koindukcyjnych . Można ich używać do dopuszczania potencjalnie nieskończonych obiektów przy zachowaniu silnej właściwości normalizacji . W silnie normalizującym (każdy program się kończy) języku programowania Charity, koindukcyjne typy danych mogą być wykorzystywane do uzyskiwania zaskakujących wyników , np . .

Zobacz też

Notatki

^ ^a ^b Philip Wadler: Typy rekurencyjne za darmo! University of Glasgow, lipiec 1998. Wersja robocza.
^ Robin Cockett: Myśli charytatywne ( ps.gz )

Linki zewnętrzne

Programowanie kategorialne z typami indukcyjnymi i koindukcyjnymi firmy Varmo Vene
Typy rekurencyjne za darmo! Philip Wadler, University of Glasgow, 1990-2014.
Początkowa algebra i końcowa semantyka koalgebry dla współbieżności JJMM Rutten i D. Turi
Inicjalność i celowość z CLiki
Wpisani tłumacze końcowi bez tagów autorstwa Olega Kiselyova

[free-rectypes-1] Philip Wadler: Typy rekurencyjne za darmo! University of Glasgow, lipiec 1998. Wersja robocza.

[2] Robin Cockett: Myśli charytatywne ( ps.gz )