Nadużywanie algebry algebraicznych typów danych - dlaczego to działa?

Wyrażenie „algebraiczne” dla typów danych algebraicznych wygląda bardzo sugestywnie dla kogoś z doświadczeniem w matematyce. Pozwól mi wyjaśnić, co mam na myśli.

Po zdefiniowaniu podstawowych typów

• Produkt •
• Unia +
• Singel X
• Jednostka 1

i używając skrótów X²dla X•Xi 2Xdla X+Xet cetera, możemy następnie zdefiniować wyrażenia algebraiczne dla np. list połączonych

data List a = Nil | Cons a (List a) ↔ L = 1 + X • L

i drzewa binarne:

data Tree a = Nil | Branch a (Tree a) (Tree a) ↔ T = 1 + X • T²

Teraz moim pierwszym instynktem jako matematyka jest zwariowanie z tymi wyrażeniami i próba rozwiązania dla Li T. Mógłbym to zrobić poprzez wielokrotne zastępowanie, ale znacznie łatwiejsze jest nadużywanie horroru w notacji i udawanie, że mogę go dowolnie zmieniać. Na przykład dla połączonej listy:

L = 1 + X • L

(1 - X) • L = 1

L = 1 / (1 - X) = 1 + X + X² + X³ + ...

gdzie użyłem rozszerzenia szeregu mocy 1 / (1 - X)w całkowicie nieuzasadniony sposób, aby uzyskać interesujący wynik, a mianowicie, że Ltyp jest albo Nilzawiera 1 element, albo zawiera 2 elementy, lub 3 itd.

Staje się bardziej interesujący, jeśli robimy to dla drzew binarnych:

T = 1 + X • T²

X • T² - T + 1 = 0

T = (1 - √(1 - 4 • X)) / (2 • X)

T = 1 + X + 2 • X² + 5 • X³ + 14 • X⁴ + ...

ponownie, używając rozszerzenia serii mocy (wykonanego z Wolfram Alpha ). To wyraża nieoczywisty (dla mnie) fakt, że istnieje tylko jedno drzewo binarne z 1 elementem, 2 drzewa binarne z dwoma elementami (drugi element może znajdować się na lewej lub prawej gałęzi), 5 drzew binarnych z trzema elementami itp. .

Więc moje pytanie brzmi - co ja tu robię? Operacje te wydają się nieuzasadnione (co to właściwie jest pierwiastek kwadratowy typu danych algebraicznych?), Ale prowadzą do sensownych wyników. czy iloraz dwóch algebraicznych typów danych ma jakieś znaczenie w informatyce, czy jest to tylko sztuczka notacyjna?

A może, co ciekawsze, czy można rozszerzyć te pomysły? Czy istnieje teoria algebry typów, która pozwala na przykład na dowolne funkcje na typach, czy też typy wymagają reprezentacji szeregów mocy? Jeśli potrafisz zdefiniować klasę funkcji, to czy ich składanie ma jakieś znaczenie?

Zrzeczenie się: Wiele z tych rzeczy nie działa całkiem dobrze, gdy bierzesz pod uwagę ⊥, więc rażąco zignoruję to ze względu na prostotę.

Kilka początkowych punktów:

• Zauważ, że „unia” nie jest chyba najlepsze określenie dla A + B - to tutaj konkretnie rozłączne unia z dwóch rodzajów, ponieważ obie strony wyróżniają nawet jeśli ich typy są takie same. Co jest warte, bardziej powszechnym terminem jest po prostu „typ sumy”.

• Typy singletonów to w rzeczywistości wszystkie typy jednostek. Zachowują się identycznie podczas manipulacji algebraicznych, a co ważniejsze, ilość obecnych informacji jest nadal zachowana.

• Prawdopodobnie chcesz również typ zerowy. Haskell zapewnia, że ​​jako Void. Nie ma wartości, których typ wynosi zero, podobnie jak jedna wartość, której typ jest jeden.

Wciąż brakuje tu jednej ważnej operacji, ale zaraz do niej wrócę.

Jak zapewne zauważyłeś, Haskell ma tendencję do zapożyczania koncepcji z teorii kategorii, a wszystkie powyższe mają bardzo prostą interpretację jako taką:

• Biorąc pod uwagę obiekty A i B w Hask , ich iloczyn A × B jest unikalnym (aż do izomorfizmu) typem, który pozwala na dwie projekcje fst : A × B → A i snd : A × B → B, gdzie dany dowolny typ C i funkcje f : C → A, g : C → B można zdefiniować parowanie f &&& g : C → A × B tak, że fst ∘ (f&& g) = f i podobnie dla g . Parametryzacja gwarantuje automatyczne uniwersalne właściwości, a mój mniej subtelny wybór nazw powinien dać ci pomysł. (&&&)Operator definiuje się Control.Arrowprzez sposób.

• Podwójnym z powyższych jest koprodukt A + B z zastrzykami inl : A → A + B i inr : B → A + B, gdzie biorąc pod uwagę dowolny typ C i funkcje f : A → C, g : B → C, możesz zdefiniuj copairing f ||| g : A + B → C tak, że zachowują się oczywiste równoważności. Ponownie, parametryczność gwarantuje większość trudnych części automatycznie. W tym przypadku są po prostu standardowych iniekcji Lefti Righti copairing jest funkcją either.

Wiele właściwości typów produktów i sum można wyprowadzić z powyższego. Zauważ, że każdy typ singletonu jest obiektem końcowym Hask, a każdy pusty typ jest obiektem początkowym.

Wracając do wyżej wspomnianej operacji brakującej, w kartezjańskiej zamkniętej kategorii masz obiekty wykładnicze odpowiadające strzałkom tej kategorii. Nasze strzały są funkcjami, nasze obiekty są rodzajami z rodzaju *, a rodzaj A -> Brzeczywiście zachowuje się jak B ^A w kontekście algebraicznej manipulacji typami. Jeśli nie jest oczywiste, dlaczego tak się dzieje, rozważ typ Bool -> A. Przy tylko dwóch możliwych wejściach funkcja tego typu jest izomorficzna w stosunku do dwóch wartości typu A, tj (A, A). Ponieważ Maybe Bool -> Amamy trzy możliwe dane wejściowe i tak dalej. Zauważ też, że jeśli zmienimy sformułowanie powyższej definicji copairing w celu użycia notacji algebraicznej, otrzymamy tożsamość C ^A × C ^B = C^{A + B} .

Jeśli chodzi o to, dlaczego to wszystko ma sens - a w szczególności dlaczego użycie rozszerzenia mocy jest uzasadnione - zauważ, że wiele z powyższych odnosi się do „mieszkańców” danego typu (tj. Odrębnych wartości mających ten typ) w kolejności aby zademonstrować zachowanie algebraiczne. Aby wyraźnie przedstawić tę perspektywę:

• Typ produktu (A, B)reprezentuje wartość dla każdego Ai Bwzięty niezależnie. Tak więc dla każdej stałej wartości a :: Aistnieje jedna wartość typu (A, B)dla każdego mieszkańca B. Jest to oczywiście produkt kartezjański, a liczba mieszkańców danego rodzaju produktu jest iloczynem liczby mieszkańców czynników.

• Typ sumy Either A Breprezentuje wartość z jednej Alub Bz wyróżnieniem lewej i prawej gałęzi. Jak wspomniano wcześniej, jest to rozłączny związek, a liczba mieszkańców typu suma jest sumą liczby mieszkańców szczytów.

• Typ wykładniczy B -> Areprezentuje odwzorowanie wartości typu Bna wartości typu A. Dla każdego ustalonego argumentu można mu przypisać b :: Bdowolną wartość A; wartość typu B -> Awybiera jedno takie mapowanie dla każdego wejścia, co jest równoważne iloczynowi tylu kopii, Aile Bma mieszkańców, stąd potęgowanie.

Chociaż początkowo kuszące jest traktowanie typów jako zbiorów, to w rzeczywistości nie działa zbyt dobrze w tym kontekście - mamy rozłączne połączenie, a nie standardowe połączenie zbiorów, nie ma oczywistej interpretacji przecięcia ani wielu innych operacji na zestawach, a my zwykle nie przejmuję się ustawieniem członkostwa (pozostawiając to sprawdzaniu typów).

Z drugiej strony powyższe konstrukcje spędzają dużo czasu na rozmowach o liczeniu mieszkańców, a wyliczenie możliwych wartości danego typu jest tutaj użyteczną koncepcją. To szybko prowadzi nas do kombinatoryki wyliczeniowej , a jeśli zajrzysz do powiązanego artykułu w Wikipedii, zauważysz, że jedną z pierwszych rzeczy, które robi, jest zdefiniowanie „par” i „związków” w dokładnie takim samym sensie, jak typy produktów i sumy na podstawie generując funkcje , robi to samo dla „sekwencji” identycznych z listami Haskella przy użyciu dokładnie tej samej techniki, co ty.

Edycja: Aha, a oto szybki bonus, który moim zdaniem pokazuje uderzająco ten punkt. Wspomniałeś w komentarzu, że dla typu drzewa T = 1 + T^2możesz uzyskać tożsamość T^6 = 1, co jest oczywiście błędne. Tak jednak się T^7 = T dzieje , a biject między drzewami i siedmioma krotkami drzew można zbudować bezpośrednio, por. „Siedem drzew w jednym” Andreasa Blassa .

Edycja × 2: Jeśli chodzi o konstrukcję „pochodną typu”, o której mowa w innych odpowiedziach, możesz także polubić ten artykuł tego samego autora, który dalej rozwija ten pomysł, w tym pojęcia podziału i inne ciekawe rzeczy.

Drzewa binarne są zdefiniowane przez równanie T=1+XT^2w semirowaniu typów. Przez konstrukcję T=(1-sqrt(1-4X))/(2X)jest zdefiniowane przez to samo równanie w semirowaniu liczb zespolonych. Biorąc pod uwagę, że rozwiązujemy to samo równanie w tej samej klasie struktury algebraicznej, nie powinno dziwić, że widzimy pewne podobieństwa.

Problem polega na tym, że gdy rozumujemy wielomiany w semirowaniu liczb zespolonych, zwykle wykorzystujemy fakt, że liczby zespolone tworzą pierścień, a nawet pole, więc używamy operacji takich jak odejmowanie, które nie mają zastosowania do semirowania. Ale często możemy wyeliminować odejmowanie naszych argumentów, jeśli mamy regułę, która pozwala nam anulować z obu stron równania. Jest to coś, co udowodnili Fiore i Leinster, pokazując, że wiele argumentów dotyczących pierścieni można przenieść na półprzezroczystości.

Oznacza to, że wiele wiedzy matematycznej na temat pierścieni można niezawodnie przenieść na typy. W rezultacie niektóre argumenty dotyczące liczb zespolonych lub szeregów potęg (w pierścieniu formalnych szeregów potęg) mogą zostać przeniesione na typy w całkowicie rygorystyczny sposób.

Jednak w tej historii jest coś więcej. To jedno, aby udowodnić, że dwa typy są równe (powiedzmy), pokazując, że dwie serie mocy są równe. Ale możesz także wydedukować informacje o typach, sprawdzając warunki w serii mocy. Nie jestem pewien, jakie powinno być formalne oświadczenie. (Polecam Brent Yorgey za papier na gatunki kombinatorycznych dla niektórych prac, który jest ściśle związany ale gatunki są nie takie same jak typy).

Zdumiewa mnie, że to, co odkryłeś, można rozszerzyć na rachunek różniczkowy. Twierdzenia o rachunku różniczkowym i całkowym można przełożyć na semirowanie typów. W rzeczywistości nawet argumenty dotyczące różnic skończonych mogą zostać przeniesione i okazuje się, że klasyczne twierdzenia z analizy numerycznej mają interpretacje w teorii typów.

Baw się dobrze!

Wydaje się, że wszystko, co robisz, to rozszerzanie relacji powtarzalności.

L = 1 + X • L
L = 1 + X • (1 + X • (1 + X • (1 + X • ...)))
  = 1 + X + X^2 + X^3 + X^4 ...

T = 1 + X • T^2
L = 1 + X • (1 + X • (1 + X • (1 + X • ...^2)^2)^2)^2
  = 1 + X + 2 • X^2 + 5 • X^3 + 14 • X^4 + ...

A ponieważ reguły operacji na typach działają podobnie jak reguły operacji arytmetycznych, możesz użyć środków algebraicznych, aby pomóc Ci dowiedzieć się, jak rozwinąć relację powtarzalności (ponieważ nie jest to oczywiste).

Nie mam pełnej odpowiedzi, ale te manipulacje zwykle „po prostu działają”. Odpowiednim referatem mogą być obiekty kategorii jako liczby zespolone według Fiore'a i Leinstera - natknąłem się na to podczas czytania bloga sigfpe na podobny temat ; reszta tego bloga to kopalnia złota dla podobnych pomysłów i warto to sprawdzić!

Nawiasem mówiąc, możesz także różnicować typy danych - dzięki temu otrzymasz odpowiedni zamek błyskawiczny dla typu danych!

Algebra procesów komunikacyjnych (ACP) dotyczy podobnych rodzajów wyrażeń dla procesów. Oferuje dodawanie i mnożenie jako operatorów wyboru i sekwencji, wraz z powiązanymi elementami neutralnymi. Na ich podstawie istnieją operatory dla innych konstrukcji, takich jak równoległość i zakłócenia. Zobacz http://en.wikipedia.org/wiki/Algebra_of_Communicating_Processes . Istnieje również artykuł online o nazwie „Krótka historia algebry procesów”.

Pracuję nad rozszerzeniem języków programowania za pomocą ACP. W kwietniu ubiegłego roku przedstawiłem artykuł badawczy na Scala Days 2012, dostępny pod adresem http://code.google.com/p/subscript/

Na konferencji zademonstrowałem debuger z równoległą rekursywną specyfikacją torby:

Torba = A; (Torba i a)

gdzie A i stanowisko dla działań wejściowych i wyjściowych; średnik i ampersand oznaczają sekwencję i równoległość. Zobacz wideo na SkillsMatter, dostępne z poprzedniego linku.

Specyfikacja torby bardziej porównywalna do

L = 1 + X • L

byłoby

B = 1 + X&B

ACP definiuje równoległość pod względem wyboru i sekwencji za pomocą aksjomatów; zobacz artykuł w Wikipedii. Zastanawiam się, po co byłaby analogia torby

L = 1 / (1-X)

Programowanie w stylu ACP jest przydatne dla parserów tekstu i kontrolerów GUI. Specyfikacje takie jak

searchCommand = kliknięty (searchButton) + klawisz (Enter)

cancelCommand = kliknięty (cancelButton) + klawisz (Escape)

można zapisać bardziej zwięźle, czyniąc dwa udoskonalenia „klikniętymi” i „kluczowymi” w sposób dorozumiany (jak to, co Scala zezwala na funkcje). Dlatego możemy napisać:

searchCommand = searchButton + Enter

cancelCommand = cancelButton + Escape

Prawa strona zawiera teraz operandy, które są danymi, a nie procesami. Na tym poziomie nie trzeba wiedzieć, jakie ukryte udoskonalenia przekształcą te operandy w procesy; niekoniecznie udoskonaliliby się w działania wejściowe; zastosowanie miałyby również działania wyjściowe, np. w specyfikacji robota testowego.

Procesy uzyskują w ten sposób dane jako elementy towarzyszące; dlatego kojarzę termin „algebra pozycji”.

Serie rachunku różniczkowego i całkowego z typami

Oto kolejny drobny dodatek - kombinatoryczny wgląd w to, dlaczego współczynniki w rozwinięciu szeregu powinny „działać”, w szczególności skupiając się na szeregach, które można uzyskać za pomocą podejścia Taylora-Maclaurina z rachunku różniczkowego. Uwaga: przykładowe rozszerzenie serii manipulowanego typu listy to seria Maclaurin.

Ponieważ inne odpowiedzi i komentarze dotyczą zachowania wyrażeń typu algebraicznego (sum, produktów i wykładników), odpowiedź ta ominie ten szczegół i skoncentruje się na rachunku typu.

W tej odpowiedzi możesz zauważyć odwrócone przecinki, które powodują ciężkie podnoszenie. Są dwa powody:

• zajmujemy się tłumaczeniami z jednej dziedziny podmiotom z drugiej i wydaje się, że właściwe jest rozgraniczanie takich zagranicznych pojęć w ten sposób.
• niektóre pojęcia będą mogły zostać sformalizowane bardziej rygorystycznie, ale kształt i pomysły wydają się ważniejsze (i zajmują mniej miejsca na pisanie) niż szczegóły.

Definicja serii Maclaurin

Seria Maclaurin funkcji f : ℝ → ℝjest zdefiniowana jako

f(0) + f'(0)X + (1/2)f''(0)X² + ... + (1/n!)f⁽ⁿ⁾(0)Xⁿ + ...

gdzie f⁽ⁿ⁾oznacza nth pochodną f.

Aby móc zrozumieć serię Maclaurin interpretowaną z typami, musimy zrozumieć, w jaki sposób możemy interpretować trzy rzeczy w kontekście typów:

• (prawdopodobnie wielokrotna) pochodna
• zastosowanie funkcji do 0
• warunki jak (1/n!)

i okazuje się, że te koncepcje z analizy mają odpowiednie odpowiedniki w świecie czcionek.

Co rozumiem przez „odpowiedni odpowiednik”? Powinien mieć smak izomorfizmu - jeśli możemy zachować prawdę w obu kierunkach, fakty, które można wywnioskować w jednym kontekście, można przenieść do drugiego.

Rachunek z typami

Co więc oznacza pochodna wyrażenia typu? Okazuje się, że dla dużej i dobrze wychowanej („różnicowalnej”) klasy wyrażeń typu i funktorów istnieje naturalna operacja, która zachowuje się na tyle podobnie, aby być odpowiednią interpretacją!

Aby zepsuć punktację, operacja analogiczna do różnicowania polega na tworzeniu „kontekstów z jednym otworem”. Jest to doskonałe miejsce do dalszego rozwijania tego konkretnego punktu, ale podstawową koncepcją kontekstu z jednym otworem ( da/dx) jest to, że reprezentuje on wynik wyodrębnienia pojedynczego podelementu określonego typu ( x) z terminu (typu a), zachowując wszystkie inne informacje, w tym niezbędne do ustalenia pierwotnej lokalizacji podelementu. Na przykład, jednym ze sposobów przedstawienia kontekstu z jednym otworem dla listy są dwie listy: jedna dla elementów, które pojawiły się przed wyodrębnioną, i jedna dla elementów, które pojawiły się później.

Motywacja do identyfikacji tej operacji z różnicowaniem wynika z następujących obserwacji. Piszemy, da/dxaby oznaczać typ kontekstów z jednym otworem dla typu az otworem typu x.

d1/dx = 0
dx/dx = 1
d(a + b)/dx = da/dx + db/dx
d(a × b)/dx = a × db/dx + b × da/dx
d(g(f(x))/dx = d(g(y))/dy[f(x)/a] × df(x)/dx

Tu 1i 0reprezentują typy z dokładnie jednym i dokładnie zerowy mieszkańców, odpowiednio, a +i ×reprezentują typy sum i towarowych, jak zwykle. fi gsą używane do reprezentowania funkcji typu lub [f(x)/a]form wyrażeń typu, i oznaczają operację podstawienia f(x)każdego aw poprzednim wyrażeniu.

Można to zapisać w stylu bez punktów, pisząc, f'że oznacza funkcję pochodną funkcji typu f, a zatem:

(x ↦ 1)' = x ↦ 0
(x ↦ x)' = x ↦ 1
(f + g)' = f' + g'
(f × g)' = f × g' + g × f'
(g ∘ f)' = (g' ∘ f) × f'

co może być lepsze.

Uwaga: równości mogą być rygorystyczne i dokładne, jeśli zdefiniujemy pochodne za pomocą klas typów i funktorów izomorfizmu.

Teraz zauważamy w szczególności, że reguły w rachunku dotyczące algebraicznych operacji dodawania, mnożenia i kompozycji (często nazywane regułami sumy, iloczynu i łańcucha) są odzwierciedlone właśnie przez operację „robienia dziury”. Ponadto, podstawowe przypadki „robienia dziury” w stałym wyrażeniu lub xsam termin zachowują się również jako różnicowanie, więc przez indukcję uzyskujemy zachowanie podobne do różnicowania dla wszystkich wyrażeń typu algebraicznego.

Teraz możemy zinterpretować różnicowanie, co oznacza n„pochodna” wyrażenia typu dⁿe/dxⁿ? Jest to typ reprezentujący nkonteksty -place: terminy, które po „wypełnieniu” nterminami typu xdają wynik e. Jest jeszcze jedna kluczowa obserwacja związana z (1/n!)późniejszym.

Niezmienna część funktora typu: zastosowanie funkcji do 0

W 0świecie typów mamy już interpretację : pusty typ bez członków. Co to znaczy, z kombinatorycznego punktu widzenia, zastosować do niej funkcję typu? Mówiąc bardziej konkretnie, załóżmy, że fjest funkcją typu, jak to f(0)wygląda? Cóż, z pewnością nie mamy dostępu do niczego takiego 0, więc wszelkie konstrukcje f(x)wymagające tego xsą niedostępne. Pozostały tylko te terminy, które są dostępne pod ich nieobecność, które możemy nazwać „niezmienną” lub „stałą” częścią typu.

Dla wyraźnego przykładu weź Maybefunktor, który można przedstawić algebraicznie jako x ↦ 1 + x. Kiedy to zastosujemy 0, otrzymamy 1 + 0- to jest tak 1: jedyną możliwą wartością jest Nonewartość. Podobnie dla listy otrzymujemy tylko termin odpowiadający pustej liście.

Kiedy przywracamy go i interpretujemy typ f(0)jako liczbę, można go traktować jako liczbę, ile terminów typu f(x)(dla dowolnego x) można uzyskać bez dostępu do x: to znaczy liczby terminów „pustych” .

Podsumowując: pełna interpretacja serii Maclaurin

Obawiam się, że nie mogę wymyślić odpowiedniej bezpośredniej interpretacji (1/n!)jako typu.

Jeśli weźmiemy pod uwagę typ f⁽ⁿ⁾(0)w świetle powyższego, widzimy, że można go interpretować jako typ nkontekstów -place dla terminu typu, f(x)który jeszcze nie zawiera x - to znaczy, kiedy „integrujemy” je nrazy , wynikowy termin ma dokładnie n x s, nie więcej, nie mniej. Zatem interpretacja typu f⁽ⁿ⁾(0)jako liczby (jak we współczynnikach z serii Maclaurin f) jest po prostu zliczeniem liczby takich nkontekstów pustych miejsc. Jesteśmy już prawie na miejscu!

Ale gdzie się (1/n!)kończy? Badanie procesu różnicowania typu pokazuje nam, że po wielokrotnym zastosowaniu zachowuje „porządek” wydobywania subtermów. Weźmy na przykład pojęcie (x₀, x₁)typu x × xi operację „wykonania w nim dziury” dwa razy. Otrzymujemy obie sekwencje

(x₀, x₁)  ↝  (_₀, x₁)  ↝  (_₀, _₁)
(x₀, x₁)  ↝  (x₀, _₀)  ↝  (_₁, _₀)
(where _ represents a 'hole')

mimo że oba pochodzą z tego samego terminu, ponieważ istnieją 2! = 2sposoby na pobranie dwóch elementów z dwóch, zachowując porządek. Ogólnie istniejąn! sposoby na pobranie nelementów n. Aby więc policzyć liczbę konfiguracji typu funktora, które mają nelementy, musimy policzyć typ f⁽ⁿ⁾(0)i podzielić n!, dokładnie tak , jak w przypadku współczynników szeregu Maclaurin.

Tak więc dzielenie przez n!okazuje się być po prostu interpretowalne jak samo.

Ostatnie przemyślenia: definicje „rekurencyjne” i analityczność

Po pierwsze, niektóre spostrzeżenia:

• jeśli funkcja f: ℝ → ℝ ma pochodną, ​​pochodna ta jest unikalna
• podobnie, jeśli funkcja f: ℝ → ℝ jest analityczna, ma dokładnie jedną odpowiednią serię wielomianową

Ponieważ mamy regułę łańcucha, możemy zastosować niejawne różnicowanie , jeśli sformalizujemy pochodne typu jako klasy izomorficzne. Ale ukryte różnicowanie nie wymaga żadnych manewrów obcych, takich jak odejmowanie lub dzielenie! Możemy więc użyć go do analizy definicji typów rekurencyjnych. Oto przykład naszej listy

L(X) ≅ 1 + X × L(X)
L'(X) = X × L'(X) + L(X)

i wtedy możemy ocenić

L'(0) = L(0) = 1

aby uzyskać współczynnik z X¹serii Maclaurin.

Ale ponieważ jesteśmy przekonani, że te wyrażenia są rzeczywiście ściśle „różnicowalne”, choćby pośrednio, i ponieważ mamy korespondencję z funkcjami ℝ → ℝ, gdzie pochodne są z pewnością wyjątkowe, możemy być pewni, że nawet jeśli otrzymamy wartości za pomocą „ nielegalne ”, wynik jest prawidłowy.

Podobnie, aby użyć drugiej obserwacji, ze względu na zgodność (czy jest to homomorfizm?) Z funkcjami ℝ → ℝ, wiemy, że pod warunkiem, że jesteśmy przekonani, że funkcja ma szereg Maclaurina, jeśli możemy znaleźć dowolną serię na wszystkie powyższe zasady można zastosować, aby były rygorystyczne.

Jeśli chodzi o twoje pytanie dotyczące kompozycji funkcji, przypuszczam, że reguła łańcucha zapewnia częściową odpowiedź.

Nie jestem pewien, do ilu ADT w stylu Haskella to dotyczy, ale podejrzewam, że jest ich wiele, jeśli nie wszystkie. Odkryłem naprawdę cudowny dowód na ten fakt, ale ten margines jest zbyt mały, aby go pomieścić ...

Z pewnością jest to tylko jeden sposób, aby dowiedzieć się, co się tu dzieje i prawdopodobnie istnieje wiele innych sposobów.

Podsumowanie: TL; DR

• typ „różnicowanie” odpowiada „ zrobieniu dziury ”.
• zastosowanie funktora, aby uzyskać 0„puste” warunki dla tego funktora.
• Szeregi potęgowe Maclaurina odpowiadają zatem (nieco) rygorystycznie wyliczeniu liczby elementów typu funktora z pewną liczbą elementów.
• niejawne różnicowanie czyni to bardziej wodoszczelnym.
• wyjątkowość pochodnych i niepowtarzalność szeregów mocy oznacza, że ​​możemy fałszować detale i to działa.

Teoria typów zależnych i funkcje typu „dowolne”

Moja pierwsza odpowiedź na to pytanie była pełna pojęć, mało szczegółów i zastanawiała się nad pytaniem: „co się dzieje?”; ta odpowiedź będzie taka sama, ale skoncentrowana na pytaniu „czy możemy uzyskać funkcje dowolnego typu?”.

Jednym rozszerzeniem algebraicznych operacji sumy i iloczynu są tak zwane „duże operatory”, które reprezentują sumę i iloczyn sekwencji (lub bardziej ogólnie, sumę i iloczyn funkcji w domenie), zwykle zapisywane Σi Πodpowiednio. Zobacz zapis Sigma .

Więc suma

a₀ + a₁X + a₂X² + ...

może być napisane

Σ[i ∈ ℕ]aᵢXⁱ

gdzie ajest na przykład sekwencja liczb rzeczywistych. Produkt byłby reprezentowany podobnie z Πzamiast Σ.

Kiedy patrzysz z dystansu, ten rodzaj wyrażenia przypomina bardzo „dowolną” funkcję X; jesteśmy oczywiście ograniczeni do wyrażalnych szeregów i związanych z nimi funkcji analitycznych. Czy jest to kandydat na reprezentację w teorii typów? Zdecydowanie!

Klasą teorii typów, które mają bezpośrednie przedstawienie tych wyrażeń, jest klasa teorii typów „zależnych”: teorie z typami zależnymi. Oczywiście mamy terminy zależne od terminów, w językach takich jak Haskell z funkcjami typu i kwantyfikacją typów, terminy i typy zależne od typów. W ustawieniu zależnym dodatkowo mamy typy zależne od warunków. Haskell nie jest językiem zależnym od typu, chociaż wiele funkcji typów zależnych można symulować przez nieco torturowanie tego języka .

Curry-Howard i typy zależne

„Izomorfizm Curry'ego-Howarda” rozpoczął życie jako spostrzeżenie, że terminy i reguły oceniania typów rachunku lambda po prostu wpisanego dokładnie odpowiadają naturalnej dedukcji (sformułowanej przez Gentzena) zastosowanej do intuicyjnej logiki zdań, a typy zajmują miejsce zdań oraz warunki zastępujące dowody, mimo że oba zostały niezależnie wynalezione / odkryte. Od tego czasu jest to ogromne źródło inspiracji dla teoretyków typów. Jedną z najbardziej oczywistych rzeczy do rozważenia jest to, czy i jak tę korespondencję dla logiki zdań można rozszerzyć na logikę predykatu lub wyższego rzędu. Teorie typu zależnego początkowo powstały z tej drogi eksploracji.

Aby zapoznać się z wprowadzeniem do izomorfizmu Curry'ego-Howarda dla rachunku zwykłego rachunku lambda, zobacz tutaj . Na przykład, jeśli chcemy udowodnić A ∧ B, musimy Audowodnić B; dowód łączony to po prostu para dowodów: po jednym dla każdego spójnika.

W odliczeniu naturalnym:

Γ ⊢ A    Γ ⊢ B
Γ ⊢ A ∧ B

i w prostym typie rachunku lambda:

Γ ⊢ a : A    Γ ⊢ b : B
Γ ⊢ (a, b) : A × B

Podobne zależności istnieją dla ∨typów sum i typów →oraz typów funkcji i różnych reguł eliminacji.

Twierdzenie nie do udowodnienia (intuicyjnie fałszywe) odpowiada typowi niezamieszkanemu.

Mając na uwadze analogię typów jako zdania logiczne, możemy zacząć zastanawiać się, jak modelować predykaty w świecie typów. Istnieje wiele sposobów sformalizowania tego (patrz wprowadzenie do Intuitionistycznej teorii typów Martina-Löfa dla powszechnie stosowanego standardu), ale abstrakcyjne podejście zwykle zauważa, że ​​predykat jest jak zdanie z zmiennymi dowolnymi lub, alternatywnie, funkcja przyjmująca warunki do zdań. Jeśli pozwolimy, aby wyrażenia typu zawierały terminy, wówczas leczenie w stylu rachunku lambda natychmiast stanie się możliwe!

Biorąc pod uwagę tylko konstruktywne dowody, co stanowi dowód ∀x ∈ X.P(x)? Możemy myśleć o tym jako o funkcji dowodowej, przyjmując warunki ( x) do dowodów odpowiadających im zdań ( P(x)). Tak Członkowie (dowodów) typu (propozycja) ∀x : X.P(x)są zależne od funkcji „”, który dla każdego xw Xdają pojęcie typu P(x).

Co ∃x ∈ X.P(x)? Musimy każdy członek X, xwraz z dowodem P(x). Tak członków (dowodów) typu (propozycja) ∃x : X.P(x)są „pary utrzymaniu”: wybitnym określenie xsię X, wraz ze względu na ich rodzaj P(x).

Notacja: użyję

∀x ∈ X...

dla rzeczywistych wypowiedzi na temat członków klasy X, oraz

∀x : X...

dla wyrażeń typu odpowiadających uniwersalnej kwantyfikacji nad typem X. Podobnie dla ∃.

Uwagi kombinatoryczne: produkty i sumy

Oprócz korespondencji typów Curry'ego-Howarda z twierdzeniami, mamy kombinatoryczną zgodność typów algebraicznych z liczbami i funkcjami, co jest głównym punktem tego pytania. Na szczęście można to rozszerzyć na typy zależne przedstawione powyżej!

Użyję notacji modułu

|A|

reprezentowanie „rozmiaru” typu A, wyraźne powiązanie przedstawione w pytaniu między typami i liczbami. Zauważ, że jest to koncepcja poza teorią; Nie twierdzę, że w języku musi istnieć taki operator.

Policzmy możliwe (całkowicie zredukowane, kanoniczne) elementy typu

∀x : X.P(x)

który jest rodzajem funkcji zależnych uwzględniających warunki xtypu Xdo warunków typu P(x). Każda taka funkcja musi mieć dane wyjściowe dla każdego terminu X, a dane wyjściowe muszą być określonego typu. Dla każdego xIN X, to daje to |P(x)|„wybory” na wyjściu.

Punktem wyjścia jest

|∀x : X.P(x)| = Π[x : X]|P(x)|

co oczywiście nie czyni ogromne wiele sensu, jeśli Xjest IO (), ale ma zastosowanie do algebraicznych typów.

Podobnie termin typu

∃x : X.P(x)

Jest to typ par (x, p)z p : P(x), więc biorąc pod uwagę każdy xw Xmożemy skonstruować odpowiednią parę z jakiegokolwiek członka P(x), dając |P(x)|"wyborów.

W związku z tym,

|∃x : X.P(x)| = Σ[x : X]|P(x)|

z tymi samymi zastrzeżeniami.

Uzasadnia to powszechną notację typów zależnych w teoriach za pomocą symboli Πi Σ, i rzeczywiście, wiele teorii zaciera rozróżnienie między „dla wszystkich” i „produktem” oraz między „jest” i „sumą”, ze względu na wyżej wspomniane korespondencje.

Zbliżamy się!

Wektory: reprezentujące krotki zależne

Czy możemy teraz zakodować wyrażenia numeryczne takie jak

Σ[n ∈ ℕ]Xⁿ

jako wyrażenia typu?

Nie do końca. Chociaż możemy nieformalnie rozważyć znaczenie wyrażeń takich jak Xⁿw Haskell, gdzie Xjest typ i nliczba naturalna, jest to nadużycie zapisu; Jest to wyrażenie typu zawierający numer: wyraźnie nie poprawny wyraz.

Z drugiej strony, w przypadku typów zależnych na zdjęciu, typy zawierające liczby są właśnie tym celem; w rzeczywistości zależne krotki lub „wektory” są bardzo często cytowanym przykładem tego, w jaki sposób typy zależne mogą zapewnić pragmatyczne bezpieczeństwo na poziomie typu dla operacji takich jak dostęp do listy . Wektor jest tylko listą wraz z informacją na temat typu dotyczącą jego długości: dokładnie tym, czego szukamy dla wyrażeń typu Xⁿ.

Na czas trwania tej odpowiedzi pozwól

Vec X n

być typem nwektorów długości Xwartości -type.

Technicznie njest to, zamiast rzeczywistej liczby naturalnej, reprezentacja w systemie liczby naturalnej. Możemy reprezentować liczby naturalne ( Nat) w stylu Peano jako zero ( 0) lub następcę ( S) innej liczby naturalnej, i n ∈ ℕpiszę, ˻n˼aby oznaczać termin, w Natktórym reprezentuje n. Na przykład ˻3˼jest S (S (S 0)).

Następnie mamy

|Vec X ˻n˼| = |X|ⁿ

dla każdego n ∈ ℕ.

Typy nat: promowanie ℕ haseł do typów

Teraz możemy zakodować wyrażenia takie jak

Σ[n ∈ ℕ]Xⁿ

jako typy. To szczególne wyrażenie dałoby początek typowi, który jest oczywiście izomorficzny z typem list X, jak określono w pytaniu. (Nie tylko to, ale z teoretycznego punktu widzenia funkcja typu - która jest funktorem - biorąc Xpod uwagę powyższy typ jest naturalnie izomorficzna w stosunku do funktora List.)

Ostatnim elementem układanki dla „arbitralnych” funkcji jest sposób kodowania

f : ℕ → ℕ

wyrażenia jak

Σ[n ∈ ℕ]f(n)Xⁿ

abyśmy mogli zastosować dowolne współczynniki do szeregu mocy.

Rozumiemy już zgodność typów algebraicznych z liczbami, co pozwala nam mapować typy na liczby i funkcje typów na funkcje numeryczne. Możemy też iść w drugą stronę! - biorąc liczbę naturalną, istnieje oczywiście możliwy do zdefiniowania typ algebraiczny z tak wieloma członami terminowymi, niezależnie od tego, czy mamy typy zależne, czy nie. Możemy to łatwo udowodnić poza teorią typów przez indukcję. Potrzebujemy sposobu mapowania liczb naturalnych na typy wewnątrz systemu.

Przyjemną realizacją jest to, że gdy mamy typy zależne, dowody indukcyjne i konstrukcyjne rekurencyjne stają się bardzo podobne - w rzeczywistości są one takie same w wielu teoriach. Skoro możemy przez indukcję udowodnić, że istnieją typy, które spełniają nasze potrzeby, czy nie powinniśmy być w stanie je zbudować?

Istnieje kilka sposobów reprezentowania typów na poziomie terminu. Posłużę się tutaj wyimaginowaną notacją haskalijską *dla wszechświata typów, który zwykle uważany jest za typ w zależności od niego. ¹

Podobnie, istnieje co najmniej tyle sposobów na zanotowanie „ ℕeliminacji”, ile jest zależnych teorii typów. Użyję notacji pasującej do wzoru Haskellisha.

Musimy mapowanie, αod Natcelu *, z właściwością

∀n ∈ ℕ.|α ˻n˼| = n.

Występuje następująca pseudodefinicja.

data Zero -- empty type
data Successor a = Z | Suc a -- Successor ≅ Maybe

α : Nat -> *
α 0 = Zero
α (S n) = Successor (α n)

Widzimy więc, że działanie αzwierciadła odzwierciedla zachowanie następcy S, czyniąc z niego rodzaj homomorfizmu. Successorjest funkcją typu, która „dodaje jedną” do liczby elementów typu; to znaczy |Successor a| = 1 + |a|dla każdego ao określonym rozmiarze.

Na przykład α ˻4˼(który jest α (S (S (S (S 0))))) jest

Successor (Successor (Successor (Successor Zero)))

a warunki tego typu to

Z
Suc Z
Suc (Suc Z)
Suc (Suc (Suc Z))

daje nam dokładnie cztery elementy: |α ˻4˼| = 4.

Podobnie dla każdego n ∈ ℕmamy

|α ˻n˼| = n

jako wymagane.

1. Wiele teorii wymaga, aby członkowie *byli zwykłymi przedstawicielami typów, a operacja jest zapewniona jako jawne odwzorowanie terminów typów *na powiązane z nimi typy. Inne teorie pozwalają, aby same dosłowne typy były jednostkami na poziomie terminowym.

Funkcje „arbitralne”?

Teraz mamy aparat do wyrażenia w pełni ogólnej serii mocy jako typu!

Serie

Σ[n ∈ ℕ]f(n)Xⁿ

staje się typem

∃n : Nat.α (˻f˼ n) × (Vec X n)

gdzie ˻f˼ : Nat → Natjest odpowiednia reprezentacja w języku funkcji f. Możemy to zobaczyć w następujący sposób.

|∃n : Nat.α (˻f˼ n) × (Vec X n)|
    = Σ[n : Nat]|α (˻f˼ n) × (Vec X n)|          (property of ∃ types)
    = Σ[n ∈ ℕ]|α (˻f˼ ˻n˼) × (Vec X ˻n˼)|        (switching Nat for ℕ)
    = Σ[n ∈ ℕ]|α ˻f(n)˼ × (Vec X ˻n˼)|           (applying ˻f˼ to ˻n˼)
    = Σ[n ∈ ℕ]|α ˻f(n)˼||Vec X ˻n˼|              (splitting product)
    = Σ[n ∈ ℕ]f(n)|X|ⁿ                           (properties of α and Vec)

Jak to „arbitralne”? Metodą tą ograniczamy się nie tylko do współczynników całkowitych, ale także do liczb naturalnych. Poza tym, fmoże być cokolwiek, biorąc pod uwagę język Turing Complete z typami zależnymi, możemy reprezentować dowolną funkcję analityczną o współczynnikach liczb naturalnych.

Nie badałem interakcji tego z, na przykład, przypadkiem przedstawionym w pytaniu List X ≅ 1/(1 - X)lub jaki możliwy sens takie negatywne i niecałkowate „typy” mogą mieć w tym kontekście.

Mam nadzieję, że ta odpowiedź w jakiś sposób pozwoli zbadać, jak daleko możemy posunąć się z funkcjami dowolnego typu.