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

Drzewa binarne są zdefiniowane równaniem T=1+XT^2 w semiringu typów. Przez konstrukcję, T=(1-sqrt(1-4X))/(2X) jest określone przez to samo równanie w semiringu 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.

Haczyk polega na tym, że gdy wnioskujemy o wielomianach w semiringu liczb zespolonych, zwykle używamy faktu, że liczby zespolone tworzą pierścień lub nawet pole więc znajdujemy się za pomocą operacji takich jak odejmowanie, które nie mają zastosowania do semirings. Ale często możemy wyeliminować odejmowania od naszych argumentów, jeśli mamy regułę, która pozwala nam anulować z obu stron równania. Jest to coś udowodnione przez Fiore i Leinster pokazujące, że wiele argumentów na temat pierścieni można przenieść do semiringów.

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

Wygląda na to, że wszystko, co robisz, to rozszerzanie relacji powtarzania.

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ą jak reguły operacji arytmetycznych, możesz użyć środków algebraicznych, aby pomóc ci dowiedzieć się, jak rozwinąć relację powtarzania (ponieważ nie jest to oczywiste).

Nie mam kompletnej odpowiedzi, ale te manipulacje mają tendencję do "po prostu działać". Odpowiednim artykułem mogą być Obiekty kategorii jako liczby złożone autorstwa Fiore i Leinster - natknąłem się na ten jeden podczas czytania bloga sigfpe na pokrewny temat ; reszta tego bloga to kopalnia złota dla podobnych pomysłów i jest warta sprawdzenia!

Można również różnicować typy danych, przy okazji-dzięki temu uzyskasz odpowiedni zamek dla danego typu danych!

Algebra procesów komunikacyjnych (ACP) zajmuje się podobnymi rodzajami wyrażeń dla procesów. Oferuje dodawanie i mnożenie jako operatorów wyboru i sekwencji, 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 procesu".

Pracuję nad przedłużeniem języki programowania z ACP. W kwietniu ubiegłego roku zaprezentowałem pracę badawczą na dniach Scala 2012, dostępną pod adresem http://code.google.com/p/subscript/

Na konferencji zademonstrowałem debugger uruchamiający równoległą rekurencyjną specyfikację worka:

Bag = A; (Bag&A)

Gdzie a i a oznaczają akcje wejściowe i wyjściowe; średnik i ampersand oznaczają sekwencję i równoległość. Zobacz film na SkillsMatter, osiągalny z poprzedniego linku.

Torba Specyfikacja bardziej porównywalna do

L = 1 + X * L

Byłoby

B = 1 + X & B

ACP definiuje paralelizm w kategoriach wyboru i sekwencji za pomocą aksjomatów; zobacz artykuł w Wikipedii. Ciekawe do czego by była ta torba

L = 1 / (1-X)

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

SearchCommand = clicked (searchButton) + key (Enter)

CancelCommand = clicked (cancelButton) + key (Escape)

Można zapisać bardziej zwięźle, czyniąc dwa udoskonalenia "clicked" i "key" implicite (jak to, na co pozwala Scala Z FUNKCJAMI). Stąd 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 jest konieczne wiedzieć, jakie dorozumiane udoskonalenia zamienią te operandy w procesy; nie koniecznie doprecyzuj do działań wejściowych; działania wyjściowe będą również miały zastosowanie, np. w specyfikacji robota testowego.

} procesy otrzymują w ten sposób dane jako Kompany; dlatego też używam terminu "algebra pozycji".

Teoria typów zależnych i 'arbitralne' funkcje typu

Jednym z rozszerzeń operacji algebraicznych sumy i iloczynu są tzw. operatory Duże, które reprezentują sumę i iloczyn ciągu (lub ogólniej sumę i iloczyn funkcji nad domeną) zazwyczaj zapisywane odpowiednio Σ i Π. Zobacz Sigma Notation .

Więc suma

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

Może być napisane

Σ[i ∈ ℕ]aᵢXⁱ

Gdzie a jest pewnym ciągiem liczb rzeczywistych, na przykład. Produkt byłby reprezentowany w podobny sposób za pomocą Π zamiast Σ.

Kiedy patrzysz z dystansu, tego rodzaju wyrażenie wygląda bardzo podobnie do' arbitralnej ' funkcji w X; jesteśmy oczywiście ograniczeni do serii expressible i związanych z nimi funkcji analitycznych. Czy to kandydat do reprezentacji w teorii typów? Zdecydowanie!

Klasa teorii typów, które mają bezpośrednie reprezentacje tych wyrażeń, jest klasą "zależnych" teorii typów: teorii z zależnymi typami. Naturalnie mamy terminy zależne od terminów, a w językach takich jak Haskell z funkcjami typu i kwantyfikacją typu, terminy i typy zależne od typów. W zależności od ustawienia, my dodatkowo mają typy w zależności od warunków. Haskell nie jest językiem zależnym, chociaż wiele cech typów zależnych może być symulowanych przez Torturowanie języka trochę .

Curry-Howard i typy zależne

Izomorfizm Curry 'ego-Howarda rozpoczął życie jako obserwacja, że terminy i zasady oceniania typu rachunku lambda odpowiadają dokładnie dedukcji naturalnej (sformułowanej przez Gentzena) zastosowanej do intuicjonistycznej propozycji logika, z typami zajmującymi miejsce twierdzeń, a terminami zajmującymi miejsce dowodów, mimo że oba są niezależnie wymyślone/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 w jaki sposób ta korespondencja dla logiki propositionalnej może zostać rozszerzona na logikę predykatu lub logikę wyższego rzędu. Teorie typu zależnego powstały początkowo z tej drogi poszukiwań.

Na wprowadzenie do Izomorfizm Curry ' ego-Howarda dla rachunku lambda, zobacz tutaj. Jako przykład, jeśli chcemy udowodnić {[31] } musimy udowodnić A i udowodnić B; dowód kombinowany jest po prostu parą dowodów: po jednym dla każdego spójnika.

W dedukcji naturalnej:

Γ ⊢ A    Γ ⊢ B
Γ ⊢ A ∧ B

I w rachunku lambda:

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

Podobne odpowiedniki istnieją dla typów ∨ i sum, → i typów funkcji oraz różnych reguł eliminacji.

Unprovable (intuicjonistycznie nieprawdziwe) propozycja odpowiada typowi niezamieszkanemu.

Mając na uwadze analogię typów jako logicznych propozycji, możemy zacząć rozważać, jak modelować predykaty w świecie typów. Jest wiele sposobów, w jaki zostało to sformalizowane (zob.[148]}to wprowadzenie {117]} do intuicjonistycznej teorii typów Martina-Löfa dla szeroko stosowanej normy), ale abstrakcyjne podejście zwykle zauważa, że predykat jest jak propozycja z wolnymi zmiennymi terminowymi lub, alternatywnie, funkcja przyjmująca terminy do propozycji. Jeśli pozwolimy, aby wyrażenia typu zawierały terminy, wtedy leczenie w stylu rachunku lambda natychmiast prezentuje się jako możliwość!

Biorąc pod uwagę tylko konstruktywne dowody, co stanowi dowód ∀x ∈ X.P(x)? Możemy myśleć o niej jako o funkcji dowodu, biorąc terminy (x) do dowodów odpowiadających im propozycji (P(x)). Tak więc członkowie (dowody) typu (propozycja) ∀x : X.P(x) są "funkcjami zależnymi", które dla każdego x W X podaj termin typu P(x).

A co z ∃x ∈ X.P(x)? Potrzebujemy każdego członka X, x, wraz z dowodem P(x). Tak więc członkowie (dowody) typu (propozycja) ∃x : X.P(x) są 'zależnymi parami': wyróżniony termin x W X, wraz z terminem typu P(x).

Notacja: Użyję

∀x ∈ X...

Dla rzeczywistych wypowiedzi o członkach klasy X i

∀x : X...

Dla wyrażeń typu odpowiadających uniwersalnym kwantyfikacja nad typem X. Podobnie dla ∃.

Rozważania kombinatoryczne: produkty i sumy

Jak również korespondencja Curry ' ego-Howarda typów z propozycjami, mamy kombinatoryczną korespondencję typów algebraicznych z liczbami i funkcjami, która jest głównym punktem tego pytania. Na szczęście można to rozszerzyć na opisane powyżej typy zależne!

Użyję notacji modularnej

|A|

Aby reprezentować "rozmiar" Typ A, w celu wyraźnego przedstawienia korespondencji opisanej w pytaniu, pomiędzy typami i liczbami. Zauważ, że jest to pojęcie spoza teorii; nie twierdzę, że musi istnieć jakikolwiek taki operator w języku.

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

∀x : X.P(x)

Który jest typem funkcji zależnych przyjmującym terminy x typu X do terminów typu P(x). Każda taka funkcja musi mieć wyjście dla każdego termu X, a to wyjście musi być określonego typu. Dla każdego x W X, to daje |P(x)| 'wybory' wyjścia.

Puenta to

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

Co oczywiście nie ma wielkiego sensu, jeśli X jest IO (), ale ma zastosowanie do typów algebraicznych.

Podobnie, termin typu

∃x : X.P(x)

Jest typem PAR (x, p) Z p : P(x), więc biorąc dowolne x W X możemy skonstruować odpowiednią parę z dowolnym członkiem P(x), dając |P(x)| "wybory".

Stąd,

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

Z tymi samymi zastrzeżeniami.

Uzasadnia to powszechną notację dla typów zależnych w teoriach wykorzystujących symbole Π i Σ, i rzeczywiście wiele teorii zaciera rozróżnienie między "dla wszystkich" i "produkt" oraz między "istnieje" i "suma", ze względu na wyżej wymienione korespondencje.

Wektory: reprezentujące zależne krotki

Czy możemy teraz kodować numerycznie wyrażenia typu

Σ[n ∈ ℕ]Xⁿ

Jako wyrażenia typu?

Z drugiej strony, z typami zależnymi na obrazku, typy zawierające liczby To właśnie punkt; 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 informacjami na poziomie typu dotyczącymi jego długości: dokładnie tego, czego szukamy dla wyrażeń typu, takich jak Xⁿ.

Na czas trwania tej odpowiedzi niech

Vec X n

Być typem długości - n wektorów X-wartości typu.

Technicznie n tutaj jest, a nie rzeczywista liczba naturalna-reprezentacja w systemie liczb naturalnych. Możemy reprezentować liczby naturalne (Nat) W Stylu Peano jako zero (0) lub następca (S) innej liczby naturalnej, a dla n ∈ ℕ piszę ˻n˼, aby oznaczać termin w Nat, który reprezentuje n. Na przykład, ˻3˼ jest S (S (S 0)).

Wtedy mamy

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

Dla dowolnych n ∈ ℕ.

Typy Nat: promowanie ℕ terminów na typy

Teraz możemy kodować wyrażenia typu

Σ[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 kategorii-teoretycznego punktu widzenia, Funkcja Typu - która jest funktorem-biorąc X do powyższego typu jest naturalnie izomorficzny do funkcji listy.)

Ostatnim elementem układanki dla 'arbitralnych' funkcji jest sposób kodowania, dla

f : ℕ → ℕ

Wyrażenia jak

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

Tak, że możemy zastosować dowolne współczynniki do szeregu potęgowego.

Rozumiemy już korespondencję typów algebraicznych z liczbami, co pozwala nam mapować od typów do liczb i typować funkcje do funkcji numerycznych. Możemy też iść w drugą stronę! - biorąc liczbę naturalną, istnieje oczywiście definiowalny Typ algebraiczny z taką liczbą członów, niezależnie od tego, czy mamy typy zależne. Możemy łatwo udowodnić to poza teorii typu przez indukcję. Potrzebujemy sposobu na mapowanie od liczb naturalnych do typów, wewnątrz systemu.

Tam jest kilka sposobów na reprezentowanie typów na poziomie terminowym. Użyję tutaj wyimaginowanej notacji Haskellisha z * dla wszechświata typów, Zwykle uważanego za typ w zależności od ustawienia.¹

Podobnie, istnieje co najmniej tyle sposobów zapisywania 'ℕ-eliminacji', ile istnieją zależne teorie typu. Użyję Haskellish pasujący do wzoru notacji.

Potrzebujemy odwzorowania, α od Nat do *, z własność

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

Wystarczy 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 α odzwierciedla zachowanie następcy S, co czyni go rodzajem homomorfizmu. Successor jest funkcją typu, która "dodaje jeden" do liczby członków typu; to jest |Successor a| = 1 + |a| dla dowolnego a o określonym rozmiarze.

Na przykład α ˻4˼ (czyli α (S (S (S (S 0))))), jest

Successor (Successor (Successor (Successor Zero)))

A terminy tego typu to

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

Dając nam dokładnie cztery żywioły: |α ˻4˼| = 4.

Podobnie dla każdego n ∈ ℕ mamy

|α ˻n˼| = n

Zgodnie z wymaganiami.

1. wiele teorii wymaga, aby członkowie * byli tylko przedstawicielami typów, a operacja jest dostarczana jako wyraźne odwzorowanie z terminów typu * do ich powiązanych typów. Inne teorie pozwalają na to, że typy dosłowne same w sobie są bytami na poziomie terminowym.

'arbitralne' funkcje?

Teraz mamy aparaturę aby wyrazić w pełni ogólną serię mocy jako typ!

Seria

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

Staje się typem

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

Gdzie ˻f˼ : Nat → Nat jest pewną odpowiednią reprezentacją w języku funkcji f. Widzimy to 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 "arbitralne" jest to? Dzięki tej metodzie ograniczamy się nie tylko do współczynników całkowitych, ale do liczb naturalnych. Poza tym, f może być czymkolwiek w ogóle, biorąc pod uwagę Turing kompletny język z typami zależnymi możemy przedstawić dowolną funkcję analityczną o współczynnikach liczb naturalnych.

Nie badałem interakcji tego z, na przykład, przypadkiem podanym w pytaniu {[110] } lub jaki możliwy sens takie negatywne i nie-całkowite "typy" mogą mieć w tym kontekście.

Miejmy nadzieję, że ta odpowiedź w jakiś sposób pomoże nam zbadać, jak daleko możemy posunąć się z dowolnymi funkcjami typu.

Rachunek i szereg Maclaurina z typami

Oto kolejny drobny dodatek-kombinatoryczny wgląd w to, dlaczego współczynniki w rozszerzaniu szeregów powinny 'działać', w szczególności koncentrując się na seriach, które mogą być wyprowadzone za pomocą podejścia Taylor-Maclaurin {81]} z rachunku różniczkowego. Uwaga: przykładowe rozszerzenie serii, które podasz, typu listy manipulowanej, to seria Maclaurina.

Ponieważ inne odpowiedzi i komentarze dotyczą zachowania wyrażeń typu algebraicznego (sumy, produkty i wykładniki), ta odpowiedź ominie ten szczegół i skupi się na rodzaju "rachunek".

Możesz zauważyć odwrócone przecinki wykonujące ciężkie podnoszenie w tej odpowiedzi. Istnieją dwa powody:

• zajmujemy się udzielaniem interpretacji z jednej dziedziny podmiotom z drugiej i wydaje się właściwe rozgraniczenie takich obcych pojęć w ten sposób.
• niektóre pojęcia będą mogły być bardziej rygorystycznie sformalizowane, ale kształt i pomysły wydają się bardziej ważne (i zajmuje mniej miejsca na pisanie) niż szczegóły.

Definicja serii Maclaurina

Szereg Maclaurina funkcji f : ℝ → ℝ definiuje się jako

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

Gdzie f⁽ⁿ⁾ oznacza npochodną f.

• a (prawdopodobnie wielokrotna) pochodna
• zastosowanie funkcja do 0
• terminy jak (1/n!)

I okazuje się, że te pojęcia z analizy mają odpowiednie odpowiedniki w świecie typów.

Co mam na myśli przez "odpowiedni odpowiednik"? Powinien mieć charakter izomorfizmu - jeśli potrafimy zachować prawdę w obu kierunkach, fakty wyprowadzalne w jednym kontekście mogą być przeniesione do drugiego.

Rachunek z typami

Więc co oznacza pochodna wyrażenia typu? Okazuje się, że że dla dużej i dobrze zachowującej się ('różniczkowalnej') klasy wyrażeń i funktorów typu istnieje operacja naturalna, która zachowuje się na tyle podobnie, że jest odpowiednią interpretacją!

Aby zepsuć puentę, analogiczną do różnicowania operacją jest tworzenie "kontekstów jednodrutowych". to jest doskonałym miejscem, aby rozwinąć ten konkretny punkt dalej, ale podstawowe pojęcie kontekstu jednego otworu (da/dx) jest to, że reprezentuje wynik ekstrakcji pojedynczego subitem określonego typu (x) od term (typu a), zachowując wszystkie inne informacje, w tym niezbędne do określenia pierwotnej lokalizacji poditemu. Na przykład jednym ze sposobów reprezentowania kontekstu jednego otworu dla listy są dwie listy: jedna dla pozycji, które pojawiły się przed wyodrębnioną, a druga dla pozycji, które pojawiły się po.

Motywacja do utożsamiania tej operacji z różnicowaniem pochodzi z następujących obserwacji. Piszemy da/dx w celu Typ jednego otworu dla typu a z 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

Tutaj, 1 i 0 reprezentują typy z dokładnie jednym i dokładnie zerowym mieszkańcem, odpowiednio, a + i × reprezentują sumy i typy produktów, jak zwykle. f i g są używane do reprezentowania funkcji typu lub formatorów wyrażeń typu, a [f(x)/a] oznacza operację zastępowania f(x) dla każdego a w poprzednim wyrażeniu.

To może być napisane w stylu wolnym od punktów, zapis f' oznaczający pochodną funkcji typu f, a więc:

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

Które mogą być preferowane.

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

teraz zauważamy w szczególności, że zasady w rachunku odnoszące się do operacji algebraicznych dodawania, mnożenia i kompozycji (często nazywane regułami Sumy, produktu i łańcucha) są odzwierciedlone dokładnie przez operacja "robienia dziury". Co więcej, przypadki bazowe "robienia dziury" w wyrażeniu stałym lub samym wyrażeniux zachowują się również jako różnicowanie, więc indukcyjnie otrzymujemy 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 n-place contexts: terms, które po wypełnieniu n terminami typu x dają e. Kolejna kluczowa obserwacja związana z "(1/n!) " pojawi się później.

Część niezmienna funktora typu: zastosowanie funkcji do 0

Mamy już interpretację dla 0 w świecie typów: Typ pusty bez członów. Co z kombinatorycznego punktu widzenia oznacza zastosowanie do niego funkcji typu? Mówiąc bardziej konkretnie, przypuśćmy, że f jest funkcją typu, jak wygląda f(0)? Cóż, na pewno nie mamy dostępu do niczego typu 0, więc wszelkie konstrukcje f(x), które wymagają x, są niedostępne. Pozostały tylko te terminy, które są dostępne w przypadku ich braku, które możemy nazwać "niezmienną" lub "stałą" częścią typu.

Dla wyraźnego przykładu, weźmy funktor Maybe, który może być reprezentowany algebraicznie jako x ↦ 1 + x. Gdy zastosujemy to do 0, otrzymujemy 1 + 0 - to tak jak 1: jedyną możliwą wartością jest wartość None. Dla listy, podobnie otrzymujemy tylko termin odpowiadający pustemu lista.

Kiedy przywrócimy i zinterpretujemy Typ f(0) jako liczbę, można ją traktować jako liczbę z ilu terminów typu f(x) (dla dowolnych x) można uzyskać bez dostępu do x: to znaczy liczbę "pustych" terminów.

Złożenie go razem: kompletna interpretacja serii Maclaurina

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

Jeśli jednak weźmiemy pod uwagę typ f⁽ⁿ⁾(0) W świetle powyższego widzimy, że może być interpretowany jako typ n-miejsce kontekstów dla terminu typu f(x), który nie zawiera jeszcze x - oznacza to, że kiedy "integrujemy" je n razy, otrzymany termin ma dokładnie n xs, nie więcej, nie mniej. Wtedy interpretacja typu f⁽ⁿ⁾(0) jako liczby (jak w współczynnikach serii Maclaurina f) jest po prostu liczbą, ile takich pustych n-miejsce kontekstów istnieje. Jesteśmy już prawie!

Ale gdzie kończy się (1/n!)? Badanie procesu "różnicowania" typu pokazuje nam, że przy wielokrotnym zastosowaniu zachowuje "porządek", w którym wydobywane są podzbiory. Na przykład, rozważmy termin (x₀, x₁) typu x × x i operację "Robienie dziury" w nim dwukrotnie. Otrzymujemy obie sekwencje

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

Mimo że oba pochodzą z tego samego terminu, ponieważ istnieją sposoby, aby wziąć dwa elementy z dwóch, zachowując porządek. Ogólnie tam są n! sposoby pobierania n elementów z n. Aby więc otrzymać liczbę konfiguracji typu functora, które mają n elementy, musimy policzyć typ f⁽ⁿ⁾(0) i podzielić przez n!, dokładnie jak w współczynnikach serii Maclaurina.

Więc dzielenie przez n! okazuje się być interpretowalne po prostu jako samo.

Myśli końcowe:' rekurencyjne ' definicje i analityczność

Po pierwsze, niektóre uwagi:

• jeśli funkcja f: ℝ → ℝ ma pochodną, pochodna ta jest unikalna
• podobnie, jeśli funkcja f: → → ℝ jest analityczna, to ma dokładnie jeden odpowiadający jej szereg wielomianowy

Ponieważ mamy regułę łańcucha, możemy użyć różnicowania implicit , jeśli sformalizujemy pochodne typu jako klasy izomorfizmu. Ale niejawne różnicowanie nie wymaga żadnych obcych manewrów, takich jak odejmowanie czy dzielenie! Więc możemy go użyć do analizy rekurencyjne definicje typów. Aby wziąć przykład z listy, mamy

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 X¹ W Serii Maclaurina.

Ale ponieważ jesteśmy pewni, że wyrażenia te są rzeczywiście ściśle "różnicowalne", jeśli tylko w sposób dorozumiany, i ponieważ mamy zgodność Z FUNKCJAMI → → ℝ, gdzie pochodne są z pewnością unikalne, możemy być pewni, że nawet jeśli uzyskamy wartości za pomocą "nielegalnych" operacji, wynik jest prawidłowy.

Teraz, podobnie, użyć drugiej obserwacji, ze względu na korespondencję (jest homomorfizm?) z funkcjami → → ℝ wiemy, że pod warunkiem, że będziemy usatysfakcjonowani, że funkcja ma szereg Maclaurina, jeśli znajdziemy dowolny szereg, zasady opisane powyżej mogą być stosowane, aby uczynić ją rygorystyczną.

Jeśli chodzi o twoje pytanie o skład funkcji, przypuszczam, że reguła łańcucha dostarcza częściowej odpowiedzi.

Nie jestem pewne, ile Haskell stylu ADTs to dotyczy, ale podejrzewam, że jest wiele, jeśli nie wszystkie. Odkryłem naprawdę cudowny dowód tego faktu, ale ten margines jest zbyt mały, aby go pomieścić...

Streszczenie: TL; DR

• Typ "różnicowanie" odpowiada "Robienie otworu ".
• zastosowanie functora do 0 daje nam 'empty-like' warunki dla tego funkcjonariusza.
• Maclaurin szereg potęgowy zatem (w pewnym sensie) rygorystycznie odpowiada wyliczeniu liczby członów typu functora z pewną liczbą elementów.
• niejawne różnicowanie sprawia, że jest to bardziej wodoszczelne.
• wyjątkowość pochodnych i wyjątkowość szeregów mocy oznacza, że możemy sfałszować szczegóły i to działa.