Missbrauch der Algebra algebraischer Datentypen - warum funktioniert das?

Der 'algebraische' Ausdruck für algebraische Datentypen sieht für jemanden mit mathematischem Hintergrund sehr suggestiv aus. Lassen Sie mich versuchen zu erklären, was ich meine.

Nachdem Sie die Grundtypen definiert haben

• Produkt •
• Union +
• Singleton X
• Einheit 1

und unter Verwendung der Kurzform X²für X•Xund 2Xfür X+Xusw. können wir dann algebraische Ausdrücke für z. B. verknüpfte Listen definieren

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

und binäre Bäume:

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

Nun, mein erster Instinkt als Mathematiker gehen Nüsse mit dieser Ausdrücken und versuchen zu lösen Lund T. Ich könnte dies durch wiederholte Substitution tun, aber es scheint viel einfacher zu sein, die Notation schrecklich zu missbrauchen und so zu tun, als könnte ich sie nach Belieben neu anordnen. Zum Beispiel für eine verknüpfte Liste:

L = 1 + X • L

(1 - X) • L = 1

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

wo ich die Potenzreihenerweiterung von 1 / (1 - X)auf völlig ungerechtfertigte Weise verwendet habe, um ein interessantes Ergebnis abzuleiten, nämlich dass ein LTyp entweder Nilist oder 1 Element enthält oder 2 Elemente enthält oder 3 usw.

Es wird interessanter, wenn wir es für Binärbäume tun:

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⁴ + ...

wieder mit der Power Series-Erweiterung (mit Wolfram Alpha ). Dies drückt die für mich nicht offensichtliche Tatsache aus, dass es nur einen Binärbaum mit 1 Element, 2 Binärbäume mit zwei Elementen (das zweite Element kann sich auf dem linken oder rechten Zweig befinden), 5 Binärbäume mit drei Elementen usw. Gibt .

Meine Frage ist also - was mache ich hier? Diese Operationen scheinen ungerechtfertigt zu sein (was genau ist die Quadratwurzel eines algebraischen Datentyps?), Aber sie führen zu vernünftigen Ergebnissen. Hat der Quotient zweier algebraischer Datentypen in der Informatik eine Bedeutung oder handelt es sich nur um einen Trick der Notation?

Und, vielleicht interessanter, ist es möglich, diese Ideen zu erweitern? Gibt es eine Theorie der Typenalgebra, die beispielsweise beliebige Funktionen für Typen zulässt, oder erfordern Typen eine Potenzreihendarstellung? Wenn Sie eine Klasse von Funktionen definieren können, hat die Zusammensetzung von Funktionen dann eine Bedeutung?

Haftungsausschluss: Vieles davon funktioniert nicht ganz richtig, wenn Sie ⊥ berücksichtigen. Ich werde dies der Einfachheit halber offenkundig ignorieren.

Einige erste Punkte:

• Beachten Sie, dass "Vereinigung" hier wahrscheinlich nicht der beste Begriff für A + B ist - dies ist speziell eine disjunkte Vereinigung der beiden Typen, da die beiden Seiten unterschieden werden, selbst wenn ihre Typen gleich sind. Für das, was es wert ist, ist der häufigere Begriff einfach "Summentyp".

• Singleton-Typen sind praktisch alle Einheitentypen. Sie verhalten sich bei algebraischen Manipulationen identisch, und was noch wichtiger ist, die Menge der vorhandenen Informationen bleibt erhalten.

• Sie möchten wahrscheinlich auch einen Nulltyp. Haskell bietet das als Void. Es gibt keine Werte, deren Typ Null ist, genauso wie es einen Wert gibt, dessen Typ Eins ist.

Hier fehlt noch eine große Operation, aber ich werde gleich darauf zurückkommen.

Wie Sie wahrscheinlich bemerkt haben, neigt Haskell dazu, Konzepte aus der Kategorietheorie auszuleihen, und all das hat eine sehr einfache Interpretation als solche:

• Bei gegebenen Objekten A und B in Hask ist ihr Produkt A × B der eindeutige Typ (bis zum Isomorphismus), der zwei Projektionen fst ermöglicht : A × B → A und snd : A × B → B, wobei ein beliebiger Typ C und Funktionen f gegeben sind : C → A, g : C → B Sie können die Paarung f &&& g : C → A × B so definieren, dass fst ∘ (f &&& g) = f und ebenfalls für g . Parametrizität garantiert die universellen Eigenschaften automatisch und meine weniger subtile Namenswahl sollte Ihnen die Idee geben. Der (&&&)Operator ist Control.Arrowübrigens in definiert.

• Das Doppelte der obigen ist das Nebenprodukt A + B mit Injektionen inl : A → A + B und inr : B → A + B, wobei jeder Typ C und jede Funktion f : A → C, g : B → C gegeben ist Definieren Sie die Copairing f ||| g : A + B → C, so dass die offensichtlichen Äquivalenzen gelten. Auch hier garantiert die Parametrizität die meisten kniffligen Teile automatisch. In diesem Fall sind die Standardinjektionen einfach Leftund Rightund die Kopairing ist die Funktion either.

Viele der Eigenschaften von Produkt- und Summentypen können aus den obigen abgeleitet werden. Beachten Sie, dass jeder Singleton-Typ ein Terminalobjekt von Hask ist und jeder leere Typ ein Anfangsobjekt.

Zurück zu der oben genannten fehlenden Operation: In einer kartesischen geschlossenen Kategorie haben Sie exponentielle Objekte , die Pfeilen der Kategorie entsprechen. Unsere Pfeile sind Funktionen, unsere Objekte sind Typen mit Art *, und der Typ A -> Bverhält sich im Kontext der algebraischen Manipulation von Typen tatsächlich wie B ^A. Wenn es nicht offensichtlich ist, warum dies gelten sollte, ziehen Sie den Typ in Betracht Bool -> A. Mit nur zwei möglichen Eingaben ist eine Funktion dieses Typs isomorph zu zwei Werten des Typs A, d (A, A). H. Denn Maybe Bool -> Awir haben drei mögliche Eingaben und so weiter. Beachten Sie auch, dass wir die Identität C ^A × C ^B = C erhalten , wenn wir die obige Copairing-Definition umformulieren, um die algebraische Notation zu verwenden^{A + B} .

Was den Grund betrifft, warum dies alles sinnvoll ist - und insbesondere, warum Ihre Verwendung der Potenzreihenerweiterung gerechtfertigt ist -, beachten Sie, dass sich ein Großteil der oben genannten Punkte auf die "Einwohner" eines Typs (dh unterschiedliche Werte mit diesem Typ) in der Reihenfolge bezieht um das algebraische Verhalten zu demonstrieren. Um diese Perspektive deutlich zu machen:

• Der Produkttyp (A, B)repräsentiert jeweils einen Wert von Aund B, unabhängig voneinander. Für jeden festen Wert a :: Agibt es also einen Typwert (A, B)für jeden Einwohner von B. Dies ist natürlich das kartesische Produkt, und die Anzahl der Einwohner des Produkttyps ist das Produkt der Anzahl der Einwohner der Faktoren.

• Der Summentyp Either A Brepräsentiert einen Wert von entweder Aoder B, wobei der linke und der rechte Zweig unterschieden werden. Wie bereits erwähnt, handelt es sich um eine disjunkte Vereinigung, und die Anzahl der Einwohner des Summentyps ist die Summe der Anzahl der Einwohner der Summanden.

• Der Exponentialtyp B -> Arepräsentiert eine Zuordnung von Typwerten Bzu Typwerten A. Für jedes feste Argument b :: Bkann ihm ein beliebiger Wert von Azugewiesen werden. Ein Wert vom Typ B -> Awählt für jede Eingabe eine solche Zuordnung aus, was einem Produkt von so vielen Kopien Awie BEinwohner entspricht, daher die Potenzierung.

Während es zunächst verlockend ist, Typen als Mengen zu behandeln, funktioniert dies in diesem Zusammenhang nicht sehr gut - wir haben eher eine disjunkte Vereinigung als die Standardvereinigung von Mengen, aber es gibt keine offensichtliche Interpretation von Schnittmengen oder vielen anderen Mengenoperationen, und wir Die festgelegte Mitgliedschaft ist normalerweise nicht wichtig (überlassen Sie dies der Typprüfung).

Andererseits verbringen die obigen Konstruktionen viel Zeit damit, über das Zählen von Einwohnern zu sprechen , und das Aufzählen der möglichen Werte eines Typs ist hier ein nützliches Konzept. Das führt uns schnell zu einer Aufzählungskombinatorik , und wenn Sie den verlinkten Wikipedia-Artikel konsultieren, werden Sie feststellen, dass eines der ersten Dinge darin besteht, "Paare" und "Gewerkschaften" im gleichen Sinne wie Produkt- und Summentypen zu definieren Wenn Sie Funktionen generieren , wird dies auch für "Sequenzen" ausgeführt, die mit Haskells Listen identisch sind, und zwar mit genau der gleichen Technik wie Sie.

Edit: Oh, und hier ist ein kurzer Bonus, der meiner Meinung nach den Punkt auffallend demonstriert. Sie haben in einem Kommentar erwähnt, dass Sie für einen T = 1 + T^2Baumtyp die Identität ableiten können T^6 = 1, was eindeutig falsch ist. Gilt T^7 = T jedoch , und eine Bijektion zwischen Bäumen und sieben Tupeln von Bäumen kann direkt konstruiert werden, vgl. Andreas Blass '"Sieben Bäume in einem" .

Bearbeiten × 2: Zum Thema der Konstruktion "Ableitung eines Typs", die in anderen Antworten erwähnt wird, könnte Ihnen auch dieses Papier desselben Autors gefallen, das weiter auf der Idee aufbaut, einschließlich der Begriffe der Teilung und anderer interessanter Dinge.

Binärbäume werden durch die Gleichung T=1+XT^2im Semiring von Typen definiert. Konstruktionsbedingt T=(1-sqrt(1-4X))/(2X)wird durch die gleiche Gleichung beim Semiren komplexer Zahlen definiert. Angesichts der Tatsache, dass wir dieselbe Gleichung in derselben Klasse algebraischer Strukturen lösen, sollte es eigentlich nicht überraschen, dass wir einige Ähnlichkeiten sehen.

Der Haken ist, dass wir, wenn wir über Polynome beim Semiren komplexer Zahlen nachdenken, normalerweise die Tatsache verwenden, dass die komplexen Zahlen einen Ring oder sogar ein Feld bilden, sodass wir Operationen wie Subtraktion verwenden, die nicht für Semiringe gelten. Aber wir können oft Subtraktionen von unseren Argumenten eliminieren, wenn wir eine Regel haben, die es uns erlaubt, von beiden Seiten einer Gleichung abzubrechen. Dies ist die Art von Dingen, die von Fiore und Leinster bewiesen wurden und die zeigen, dass viele Argumente über Ringe auf Semirings übertragen werden können.

Dies bedeutet, dass viele Ihrer mathematischen Kenntnisse über Ringe zuverlässig auf Typen übertragen werden können. Infolgedessen können einige Argumente mit komplexen Zahlen oder Potenzreihen (im Ring der formalen Potenzreihen) auf völlig strenge Weise auf Typen übertragen werden.

Die Geschichte enthält jedoch noch mehr. Es ist eine Sache, zu beweisen, dass zwei Typen gleich sind (sagen wir), indem gezeigt wird, dass zwei Potenzreihen gleich sind. Sie können jedoch auch Informationen zu Typen ableiten, indem Sie die Begriffe in der Potenzreihe überprüfen. Ich bin mir nicht sicher, wie die formelle Erklärung hier lauten soll. (Ich empfehle Brent Yorgey das Papier auf kombinatorische Art für einige Arbeit , die eng verwandt ist , aber Arten sind nicht die gleichen wie Typen.)

Was ich absolut umwerfend finde, ist, dass das, was Sie entdeckt haben, auf den Kalkül ausgedehnt werden kann. Theoreme über die Analysis können auf das Semiring von Typen übertragen werden. Tatsächlich können sogar Argumente über endliche Differenzen übertragen werden, und Sie stellen fest, dass klassische Theoreme aus der numerischen Analyse Interpretationen in der Typentheorie haben.

Habe Spaß!

Es scheint, dass Sie nur die Wiederholungsbeziehung erweitern.

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 + ...

Und da die Regeln für die Operationen für die Typen wie die Regeln für arithmetische Operationen funktionieren, können Sie algebraische Mittel verwenden, um herauszufinden, wie die Wiederholungsbeziehung erweitert werden kann (da dies nicht offensichtlich ist).

Ich habe keine vollständige Antwort, aber diese Manipulationen funktionieren normalerweise nur. Ein relevantes Papier könnten Objekte von Kategorien als komplexe Zahlen von Fiore und Leinster sein - ich bin auf dieses gestoßen, als ich den Blog von sigfpe zu einem verwandten Thema gelesen habe ; Der Rest dieses Blogs ist eine Goldmine für ähnliche Ideen und einen Besuch wert!

Sie können übrigens auch Datentypen unterscheiden - so erhalten Sie den passenden Reißverschluss für den Datentyp!

Die Algebra der kommunizierenden Prozesse (ACP) behandelt ähnliche Arten von Ausdrücken für Prozesse. Es bietet Addition und Multiplikation als Operatoren für Auswahl und Reihenfolge mit zugehörigen neutralen Elementen. Basierend auf diesen gibt es Operatoren für andere Konstrukte wie Parallelität und Störung. Siehe http://en.wikipedia.org/wiki/Algebra_of_Communicating_Processes . Es gibt auch ein Online-Papier mit dem Titel "Eine kurze Geschichte der Prozessalgebra".

Ich arbeite daran, Programmiersprachen mit ACP zu erweitern. Letzten April habe ich auf den Scala Days 2012 ein Forschungspapier vorgestellt, das unter http://code.google.com/p/subscript/ verfügbar ist.

Auf der Konferenz habe ich einen Debugger demonstriert, der eine parallele rekursive Spezifikation einer Tasche ausführt:

Tasche = A; (Tasche & a)

wobei A und a für Eingabe- und Ausgabeaktionen stehen; Das Semikolon und das kaufmännische Und stehen für Sequenz und Parallelität. Sehen Sie sich das Video bei SkillsMatter an, das über den vorherigen Link erreichbar ist.

Eine Taschenspezifikation, die vergleichbarer ist mit

L = 1 + X • L.

wäre

B = 1 + X & B.

ACP definiert Parallelität in Bezug auf Auswahl und Reihenfolge unter Verwendung von Axiomen; siehe den Wikipedia-Artikel. Ich frage mich, wofür die Taschenanalogie wäre

L = 1 / (1-X)

Die Programmierung im ACP-Stil ist praktisch für Textparser und GUI-Controller. Spezifikationen wie

searchCommand = geklickt (searchButton) + Taste (Enter)

cancelCommand = geklickt (cancelButton) + Taste (Escape)

kann präziser aufgeschrieben werden, indem die beiden Verfeinerungen "angeklickt" und "Schlüssel" implizit gemacht werden (wie es Scala mit Funktionen erlaubt). Daher können wir schreiben:

searchCommand = searchButton + Enter

cancelCommand = cancelButton + Escape

Die rechte Seite enthält jetzt Operanden, die Daten und keine Prozesse sind. Auf dieser Ebene ist es nicht erforderlich zu wissen, welche impliziten Verfeinerungen diese Operanden in Prozesse verwandeln. Sie würden sich nicht unbedingt zu Eingabeaktionen verfeinern. Ausgabeaktionen würden auch gelten, z. B. in der Spezifikation eines Testroboters.

Prozesse erhalten auf diese Weise Daten als Begleiter; daher präge ich den Begriff "Gegenstandsalgebra".

Kalkül- und Maclaurin-Reihen mit Typen

Hier ist eine weitere kleine Ergänzung - eine kombinatorische Einsicht, warum die Koeffizienten in einer Reihenexpansion "funktionieren" sollten, insbesondere mit Schwerpunkt auf Reihen, die unter Verwendung des Taylor-Maclaurin- Ansatzes aus der Analysis abgeleitet werden können. NB: Die Beispielserienerweiterung, die Sie für den manipulierten Listentyp angeben, ist eine Maclaurin-Serie.

Da sich andere Antworten und Kommentare mit dem Verhalten algebraischer Typausdrücke (Summen, Produkte und Exponenten) befassen, wird diese Antwort dieses Detail beseitigen und sich auf den Typ 'Kalkül' konzentrieren.

Möglicherweise stellen Sie in dieser Antwort fest, dass Anführungszeichen stark angehoben werden. Es gibt zwei Gründe:

• Wir haben es uns zur Aufgabe gemacht, Entitäten aus einem anderen Bereich Interpretationen aus einem Bereich zu geben, und es erscheint angebracht, solche ausländischen Begriffe auf diese Weise abzugrenzen.
• Einige Begriffe können strenger formalisiert werden, aber die Form und die Ideen scheinen wichtiger zu sein (und benötigen weniger Platz zum Schreiben) als die Details.

Definition der Maclaurin-Reihe

Die Maclaurin-Reihe einer Funktion f : ℝ → ℝist definiert als

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

wo f⁽ⁿ⁾bedeutet die nth Ableitung von f.

Um die Maclaurin-Reihe als mit Typen interpretiert zu verstehen, müssen wir verstehen, wie wir drei Dinge in einem Typkontext interpretieren können:

• eine (möglicherweise mehrfache) Ableitung
• Anwenden einer Funktion auf 0
• Begriffe wie (1/n!)

und es stellt sich heraus, dass diese Konzepte aus der Analyse geeignete Gegenstücke in der Schriftwelt haben.

Was meine ich mit einem "geeigneten Gegenstück"? Es sollte den Geschmack eines Isomorphismus haben - wenn wir die Wahrheit in beide Richtungen bewahren können, können in einem Kontext ableitbare Tatsachen auf den anderen übertragen werden.

Kalkül mit Typen

Was bedeutet die Ableitung eines Typausdrucks? Es stellt sich heraus, dass es für eine große und gut erzogene ('differenzierbare') Klasse von Typausdrücken und Funktoren eine natürliche Operation gibt, die sich ähnlich genug verhält, um eine geeignete Interpretation zu sein!

Um die Pointe zu verderben, besteht die Operation analog zur Differenzierung darin, "Ein-Loch-Kontexte" zu erstellen. Dies ist ein ausgezeichneter Ort, um diesen bestimmten Punkt weiter zu erweitern, aber das Grundkonzept eines Ein-Loch-Kontexts ( da/dx) besteht darin, dass es das Ergebnis des Extrahierens eines einzelnen Unterpunkts eines bestimmten Typs ( x) aus einem Begriff (des Typs a) darstellt, wobei beibehalten wird alle anderen Informationen, einschließlich der Informationen, die zur Bestimmung des ursprünglichen Standorts des Unterelements erforderlich sind. Eine Möglichkeit, einen Ein-Loch-Kontext für eine Liste darzustellen, besteht beispielsweise aus zwei Listen: eine für Elemente, die vor der extrahierten kamen, und eine für Elemente, die danach kamen.

Die Motivation, diesen Vorgang mit Differenzierung zu identifizieren, ergibt sich aus den folgenden Beobachtungen. Wir schreiben da/dx, um den Typ von Ein-Loch-Kontexten für Typ amit Loch des Typs zu bezeichnen 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

Hier 1und 0stellen Typen mit genau einer bzw. genau null Einwohner dar und +und ×repräsentieren wie üblich Summen- und Produkttypen. fund gwerden verwendet, um Typfunktionen oder Typausdrucksbildner darzustellen, und [f(x)/a]bedeuten die Operation des Ersetzens f(x)für jeden aim vorhergehenden Ausdruck.

Dies kann in einem punktfreien Stil geschrieben werden f', wobei die Ableitungsfunktion der Typfunktion bezeichnet wird f, also:

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

was vorzuziehen sein kann.

Hinweis: Die Gleichungen können streng und genau gemacht werden, wenn wir Ableitungen unter Verwendung von Isomorphismusklassen von Typen und Funktoren definieren.

Nun stellen wir insbesondere fest, dass die Regeln im Kalkül, die sich auf die algebraischen Operationen Addition, Multiplikation und Zusammensetzung beziehen (oft als Summen-, Produkt- und Kettenregeln bezeichnet), sich genau in der Operation „Loch machen“ widerspiegeln. Darüber xhinaus verhalten sich die Basisfälle des "Machens eines Lochs" in einem konstanten Ausdruck oder der Begriff selbst auch als Differenzierung, sodass wir durch Induktion ein differenzierungsähnliches Verhalten für alle algebraischen Typausdrücke erhalten.

Jetzt können wir die Differenzierung interpretieren. Was bedeutet die nAbleitung eines dⁿe/dxⁿTypausdrucks? Es ist ein Typ, der n-place-Kontexte darstellt: Begriffe, die, wenn sie mit nBegriffen des Typs 'gefüllt' sind, xeine ergeben e. Es gibt eine weitere wichtige Beobachtung im Zusammenhang mit dem (1/n!)späteren Kommen.

Der invariante Teil eines Typfunktors: Anwenden einer Funktion auf 0

Wir haben bereits eine Interpretation für 0in der Typwelt: einen leeren Typ ohne Mitglieder. Was bedeutet es aus kombinatorischer Sicht, eine Typfunktion darauf anzuwenden? Konkreter ausgedrückt: Angenommen, es fhandelt sich um eine Typfunktion. Wie sieht es f(0)aus? Nun, wir haben sicherlich keinen Zugriff auf irgendetwas vom Typ 0, so dass Konstruktionen, für f(x)die ein erforderlich xist, nicht verfügbar sind. Was bleibt, sind jene Begriffe, die in ihrer Abwesenheit zugänglich sind und die wir als "invarianten" oder "konstanten" Teil des Typs bezeichnen können.

Nehmen Sie als explizites Beispiel den MaybeFunktor, der algebraisch als dargestellt werden kann x ↦ 1 + x. Wenn wir dies anwenden 0, erhalten wir 1 + 0- es ist nur so 1: Der einzig mögliche Wert ist der NoneWert. In ähnlicher Weise erhalten wir für eine Liste nur den Begriff, der der leeren Liste entspricht.

Wenn wir bringen sie zurück und interpretieren die Art f(0)als Nummer kann es als gedacht werden Zahl , wie viele nach Art f(x)(für jede x) ohne Zugriff auf eine erhalten werden x: die, die Zahl der ‚leer-like‘ Begriffe ist .

Zusammenstellen: vollständige Interpretation einer Maclaurin-Serie

Ich fürchte, ich kann mir keine angemessene direkte Interpretation (1/n!)als Typ vorstellen.

Wenn wir jedoch den Typ f⁽ⁿ⁾(0)im Lichte des oben nGesagten betrachten , sehen wir, dass er als Typ von Ortskontexten für einen Typbegriff interpretiert werden kann, f(x)der noch kein x - das heißt, wenn wir sie nmal 'integrieren' hat der resultierende Begriff genau n x s, nicht mehr und nicht weniger. Dann ist die Interpretation des Typs f⁽ⁿ⁾(0)als Zahl (wie in den Koeffizienten der Maclaurin-Reihe von f) einfach eine Zählung der Anzahl solcher solcher Leerstellenkontexte n. Wir sind fast da!

Aber wo landet (1/n!)es? Die Untersuchung des Prozesses der Typdifferenzierung zeigt, dass bei mehrmaliger Anwendung die Reihenfolge beibehalten wird, in der Subterme extrahiert werden. Betrachten Sie zum Beispiel den Begriff (x₀, x₁)des Typs x × xund die Operation, zweimal ein Loch darin zu machen. Wir bekommen beide Sequenzen

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

obwohl beide vom selben Begriff stammen, weil es 2! = 2Möglichkeiten gibt, zwei Elemente aus zwei zu nehmen und die Ordnung zu bewahren. Im Allgemeinen gibt esn! Möglichkeiten, nElemente zu übernehmen n. Um die Anzahl der Konfigurationen eines Funktortyps mit nElementen zu ermitteln, müssen wir den Typ zählen f⁽ⁿ⁾(0)und durch dividieren n!, genau wie bei den Koeffizienten der Maclaurin-Reihe.

Das Teilen durch n!erweist sich also als einfach als sich selbst interpretierbar.

Letzte Gedanken: 'rekursive' Definitionen und Analytizität

Zunächst einige Beobachtungen:

• Wenn eine Funktion f: ℝ → ℝ eine Ableitung hat, ist diese Ableitung eindeutig
• In ähnlicher Weise hat eine Funktion f: ℝ → ℝ, die analytisch ist, genau eine entsprechende Polynomreihe

Da wir die Kettenregel haben, können wir implizite Differenzierung verwenden , wenn wir Typderivate als Isomorphismusklassen formalisieren. Die implizite Differenzierung erfordert jedoch keine außerirdischen Manöver wie Subtraktion oder Division! Wir können es also verwenden, um rekursive Typdefinitionen zu analysieren. Um Ihr Listenbeispiel zu nehmen, haben wir

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

und dann können wir auswerten

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

um den Koeffizienten von X¹in der Maclaurin-Reihe zu erhalten.

Da wir jedoch zuversichtlich sind, dass diese Ausdrücke tatsächlich, wenn auch nur implizit, streng "differenzierbar" sind, und da wir die Entsprechung mit Funktionen ℝ → ℝ haben, bei denen Ableitungen sicherlich eindeutig sind, können wir sicher sein, dass selbst wenn wir die Werte mit 'erhalten. Bei illegalen Operationen ist das Ergebnis gültig.

Nun, in ähnlicher Weise, die zweite Beobachtung zu verwenden, aufgrund der Korrespondenz (es ist ein Homomorphismus?) Mit Funktionen r → r, wissen wir , dass, wenn wir überzeugt sind , dass eine Funktion hat eine Maclaurin Serie, wenn wir finden können jede Serie an Alles in allem können die oben beschriebenen Prinzipien angewendet werden, um es streng zu machen.

Was Ihre Frage zur Zusammensetzung von Funktionen betrifft, so gibt die Kettenregel vermutlich eine teilweise Antwort.

Ich bin nicht sicher, für wie viele ADTs im Haskell-Stil dies gilt, aber ich vermute, dass es viele, wenn nicht alle sind. Ich habe einen wirklich wunderbaren Beweis für diese Tatsache gefunden, aber dieser Rand ist zu klein, um ihn aufzunehmen ...

Dies ist sicherlich nur ein Weg, um herauszufinden, was hier vor sich geht, und es gibt wahrscheinlich viele andere Wege.

Zusammenfassung: TL; DR

• Typ 'Differenzierung' entspricht ' Loch machen '.
• Wenn Sie einen Funktor anwenden, erhalten 0Sie die "leeren" Begriffe für diesen Funktor.
• Maclaurin- Potenzreihen entsprechen daher (etwas) streng der Aufzählung der Anzahl der Mitglieder eines Funktortyps mit einer bestimmten Anzahl von Elementen.
• Die implizite Differenzierung macht dies wasserdichter.
• Die Einzigartigkeit von Derivaten und die Einzigartigkeit von Potenzreihen bedeuten, dass wir die Details verfälschen können und es funktioniert.

Abhängige Typentheorie und 'beliebige' Typfunktionen

Meine erste Antwort auf diese Frage war reich an Konzepten und wenig an Details und reflektierte die Unterfrage: "Was ist los?". Diese Antwort ist dieselbe, konzentriert sich jedoch auf die Unterfrage "Können wir beliebige Typfunktionen erhalten?".

Eine Erweiterung der algebraischen Operationen von Summen- und Produkt sind die sogenannten "großen Betreiber, die die Summe und Produkt einer Sequenz darstellen (oder allgemeiner, der Summe und Produkt einer Funktion über eine Domäne) in der Regel geschrieben Σund Πjeweils. Siehe Sigma-Notation .

Also die Summe

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

könnte geschrieben werden

Σ[i ∈ ℕ]aᵢXⁱ

Wo aist zum Beispiel eine Folge von reellen Zahlen. Das Produkt würde ähnlich mit Πstatt dargestellt Σ.

Wenn Sie aus der Ferne schauen, ähnelt diese Art von Ausdruck einer 'willkürlichen' Funktion in X; Wir beschränken uns natürlich auf ausdrucksstarke Reihen und die damit verbundenen analytischen Funktionen. Ist dies ein Kandidat für eine Darstellung in einer Typentheorie? Bestimmt!

Die Klasse der Typentheorien, die diese Ausdrücke unmittelbar darstellen, ist die Klasse der 'abhängigen' Typentheorien: Theorien mit abhängigen Typen. Natürlich haben wir Begriffe, die von Begriffen abhängig sind, und in Sprachen wie Haskell mit Typfunktionen und Typquantifizierung, Begriffen und Typen, die von Typen abhängen. In einer abhängigen Einstellung haben wir zusätzlich Typen, die von Begriffen abhängen. Haskell ist keine abhängig typisierte Sprache, obwohl viele Merkmale abhängiger Typen simuliert werden können, indem die Sprache ein wenig gefoltert wird .

Curry-Howard und abhängige Typen

Der 'Curry-Howard-Isomorphismus' begann sein Leben als Beobachtung, dass die Begriffe und Typbeurteilungsregeln des einfach getippten Lambda-Kalküls genau der natürlichen Deduktion (wie von Gentzen formuliert) entsprechen, die auf die intuitionistische Aussagenlogik angewendet wird, wobei Typen die Sätze ersetzen und Begriffe, die den Platz von Beweisen einnehmen, obwohl die beiden unabhängig voneinander erfunden / entdeckt wurden. Seitdem ist es eine große Inspirationsquelle für Typentheoretiker. Eines der offensichtlichsten zu berücksichtigenden Dinge ist, ob und wie diese Entsprechung für die Aussagenlogik auf Prädikatenlogiken oder Logiken höherer Ordnung erweitert werden kann. Aus diesem Forschungsweg entstanden zunächst abhängige Typentheorien.

Eine Einführung in den Curry-Howard-Isomorphismus für einfach typisierte Lambda-Berechnungen finden Sie hier . Wenn wir zum Beispiel beweisen wollen, A ∧ Bmüssen wir beweisen Aund beweisen B; Ein kombinierter Beweis ist einfach ein Beweispaar: einer für jede Konjunktion.

In natürlicher Ableitung:

Γ ⊢ A    Γ ⊢ B
Γ ⊢ A ∧ B

und in einfach getippter Lambda-Rechnung:

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

Ähnliche Entsprechungen existieren für ∨und Summentypen →und Funktionstypen und die verschiedenen Eliminierungsregeln.

Ein unbeweisbarer (intuitionistisch falscher) Satz entspricht einem unbewohnten Typ.

Unter Berücksichtigung der Analogie von Typen als logische Sätze können wir uns überlegen, wie Prädikate in der Typwelt modelliert werden können. Es gibt viele Möglichkeiten, wie dies formalisiert wurde (siehe diese Einführung zu Martin-Löfs Intuitionistischer Typentheorie für einen weit verbreiteten Standard), aber der abstrakte Ansatz beobachtet normalerweise, dass ein Prädikat wie ein Satz mit Variablen für freie Begriffe oder alternativ wie ein Satz ist eine Funktion, die sich auf Sätze bezieht. Wenn wir zulassen, dass Typausdrücke Begriffe enthalten, bietet sich sofort eine Behandlung im Lambda-Kalkül-Stil an!

Was ist ein Beweis für nur konstruktive Beweise ∀x ∈ X.P(x)? Wir können es uns als Beweisfunktion vorstellen, indem wir Begriffe ( x) für Beweise ihrer entsprechenden Sätze verwenden ( P(x)). So Mitglieder (Proofs) des Typs (Satz) ∀x : X.P(x)sind ‚abhängige Funktionen‘, die für jeden xin Xeiner Laufzeit von Art geben P(x).

Was ist mit ∃x ∈ X.P(x)? Wir brauchen jedes Mitglied X, xzusammen mit einem Beweis P(x). Mitglieder (Beweise) des Typs (Satzes) ∃x : X.P(x)sind also 'abhängige Paare': ein definierter Begriff xin X, zusammen mit einem Begriff des Typs P(x).

Notation: Ich werde verwenden

∀x ∈ X...

für tatsächliche Aussagen über Mitglieder der Klasse X, und

∀x : X...

für Typausdrücke, die einer universellen Quantifizierung über Typ entsprechen X. Ebenso für ∃.

Kombinatorische Überlegungen: Produkte und Summen

Neben der Curry-Howard-Entsprechung von Typen mit Sätzen haben wir die kombinatorische Entsprechung von algebraischen Typen mit Zahlen und Funktionen, was der Hauptpunkt dieser Frage ist. Glücklicherweise kann dies auf die oben beschriebenen abhängigen Typen erweitert werden!

Ich werde die Modulnotation verwenden

|A|

die 'Größe' eines Typs darstellen A, die in der Frage skizzierte Entsprechung zwischen Typen und Zahlen explizit machen. Beachten Sie, dass dies ein Konzept außerhalb der Theorie ist. Ich behaupte nicht, dass es einen solchen Operator in der Sprache geben muss.

Zählen wir die möglichen (vollständig reduzierten, kanonischen) Mitglieder des Typs

∀x : X.P(x)

Dies ist die Art von abhängigen Funktionen, die Begriffe xvon Typ Xzu Begriffen von Typ nehmen P(x). Jede solche Funktion muss für jeden Term eine Ausgabe haben X, und diese Ausgabe muss von einem bestimmten Typ sein. Für jeden xin X, dann gibt dieser |P(x)|‚Wahl‘ der Ausgabe.

Die Pointe ist

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

Das macht natürlich keinen großen Sinn, Xist IO ()aber auf algebraische Typen anwendbar.

Ebenso ein Begriff vom Typ

∃x : X.P(x)

ist die Art der Paare (x, p)mit p : P(x), so gegebenen jede xin Xkönnen wir ein geeignetes Paar mit einem Mitglied des Konstrukts P(x), was |P(x)|‚Auswahl‘.

Daher,

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

mit den gleichen Einschränkungen.

Dies rechtfertigt die gemeinsame Notation für abhängige Typen in Theorien unter Verwendung der Symbole Πund Σ, und tatsächlich verwischen viele Theorien die Unterscheidung zwischen "für alle" und "Produkt" und zwischen "es gibt" und "Summe" aufgrund der oben erwähnten Entsprechungen.

Wir kommen näher!

Vektoren: Repräsentieren abhängiger Tupel

Können wir jetzt numerische Ausdrücke wie codieren?

Σ[n ∈ ℕ]Xⁿ

als Typausdrücke?

Nicht ganz. Während wir informell die Bedeutung von Ausdrücken wie Xⁿin Haskell betrachten können, wo Xes sich um einen Typ und neine natürliche Zahl handelt, handelt es sich um einen Missbrauch der Notation. Dies ist ein Typausdruck, der eine Zahl enthält: eindeutig kein gültiger Ausdruck.

Bei abhängigen Typen im Bild sind Typen mit Zahlen genau der Punkt. In der Tat sind abhängige Tupel oder 'Vektoren' ein sehr häufig genanntes Beispiel dafür, wie abhängige Typen pragmatische Sicherheit auf Typebene für Operationen wie den Listenzugriff bieten können . Ein Vektor ist nur eine Liste mit Informationen auf Typebene bezüglich seiner Länge: genau das, wonach wir für Typausdrücke wie suchen Xⁿ.

Für die Dauer dieser Antwort lassen Sie

Vec X n

sein , die Art von längen- nVektoren X; -Typ - Werten.

Technisch gesehen ist nhier eher als eine tatsächliche natürliche Zahl eine Darstellung einer natürlichen Zahl im System. Wir können natürliche Zahlen ( Nat) im Peano-Stil entweder als Null ( 0) oder als Nachfolger ( S) einer anderen natürlichen Zahl darstellen, und n ∈ ℕich schreibe ˻n˼den Begriff, in Natdem dargestellt wird n. Zum Beispiel ˻3˼ist S (S (S 0)).

Dann haben wir

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

für jeden n ∈ ℕ.

Nat-Typen: Förderung von ℕ Begriffen zu Typen

Jetzt können wir Ausdrücke wie codieren

Σ[n ∈ ℕ]Xⁿ

als Typen. Dieser spezielle Ausdruck würde zu einem Typ führen, der natürlich isomorph zu dem Typ von Listen von ist X, wie in der Frage angegeben. (Nicht nur das, sondern aus kategorietheoretischer Sicht ist die Typfunktion - die ein Funktor ist -, Xdie den obigen Typ übernimmt , natürlich isomorph zum Listenfunktor.)

Ein letztes Puzzleteil für 'beliebige' Funktionen ist das Codieren, z

f : ℕ → ℕ

Ausdrücke wie

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

damit wir beliebige Koeffizienten auf eine Potenzreihe anwenden können.

Wir verstehen bereits die Entsprechung algebraischer Typen mit Zahlen, sodass wir von Typen zu Zahlen und von Typfunktionen zu numerischen Funktionen abbilden können. Wir können auch den anderen Weg gehen! - Wenn man eine natürliche Zahl nimmt, gibt es offensichtlich einen definierbaren algebraischen Typ mit so vielen Termmitgliedern, unabhängig davon, ob wir abhängige Typen haben oder nicht. Wir können dies leicht außerhalb der Typentheorie durch Induktion beweisen . Was wir brauchen, ist eine Möglichkeit, innerhalb des Systems von natürlichen Zahlen auf Typen abzubilden .

Eine erfreuliche Erkenntnis ist, dass, sobald wir abhängige Typen haben, der Beweis durch Induktion und die Konstruktion durch Rekursion sehr ähnlich werden - tatsächlich sind sie in vielen Theorien dasselbe. Sollten wir sie nicht konstruieren können, da wir durch Induktion beweisen können, dass Typen existieren, die unsere Bedürfnisse erfüllen?

Es gibt verschiedene Möglichkeiten, Typen auf Begriffebene darzustellen. Ich werde hier eine imaginäre Haskellish-Notation mit *für das Universum der Typen verwenden, die normalerweise selbst als Typ in einer abhängigen Umgebung betrachtet wird. ¹

Ebenso gibt es mindestens so viele Möglichkeiten, " ℕ-elimination" zu notieren , wie es abhängige Typentheorien gibt. Ich werde eine Haskellish Pattern Matching Notation verwenden.

Wir brauchen eine Zuordnung αvon Natbis *zur Eigenschaft

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

Die folgende Pseudodefinition reicht aus.

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

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

Wir sehen also, dass die Wirkung von αdas Verhalten des Nachfolgers Swiderspiegelt und es zu einer Art Homomorphismus macht. Successorist eine Typfunktion, die der Anzahl der Mitglieder eines Typs 'eins' hinzufügt; das heißt, |Successor a| = 1 + |a|für alle amit einer definierten Größe.

Zum Beispiel α ˻4˼(was ist α (S (S (S (S 0))))), ist

Successor (Successor (Successor (Successor Zero)))

und die Begriffe dieses Typs sind

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

Geben Sie uns genau vier Elemente : |α ˻4˼| = 4.

Ebenso n ∈ ℕhaben wir für jeden

|α ˻n˼| = n

nach Bedarf.

1. Viele Theorien verlangen, dass die Mitglieder von *lediglich Repräsentanten von Typen sind, und eine Operation wird als explizite Zuordnung von Typbegriffen *zu den zugehörigen Typen bereitgestellt . Andere Theorien erlauben es den Literaltypen selbst, Entitäten auf Termebene zu sein.

"Beliebige" Funktionen?

Jetzt haben wir den Apparat, eine vollständig allgemeine Potenzreihe als Typ auszudrücken!

Die Serie

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

wird zum Typ

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

Wo ˻f˼ : Nat → Natist eine geeignete Darstellung in der Sprache der Funktion f. Wir können dies wie folgt sehen.

|∃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)

Wie "willkürlich" ist das? Wir beschränken uns bei dieser Methode nicht nur auf ganzzahlige Koeffizienten, sondern auch auf natürliche Zahlen. Abgesehen fdavon kann bei einer Turing Complete- Sprache mit abhängigen Typen alles möglich sein, und wir können jede analytische Funktion mit natürlichen Zahlenkoeffizienten darstellen.

Ich habe die Wechselwirkung davon zum Beispiel mit dem Fall nicht untersucht, der in der Frage angegeben wurde, List X ≅ 1/(1 - X)oder welchen möglichen Sinn solche negativen und nicht ganzzahligen "Typen" in diesem Zusammenhang haben könnten.

Hoffentlich hilft diese Antwort dabei, herauszufinden, wie weit wir mit Funktionen beliebigen Typs gehen können.