Ich habe den Begriff "Kohlegebren" in funktionalen Programmier- und PLT-Kreisen mehrmals gehört, insbesondere wenn es um Objekte, Comonaden, Linsen und dergleichen geht. Wenn Sie diesen Begriff googeln, erhalten Sie Seiten mit mathematischen Beschreibungen dieser Strukturen, die für mich so gut wie unverständlich sind. Kann jemand bitte erklären, was Kohlegebren im Kontext der Programmierung bedeuten, welche Bedeutung sie haben und wie sie sich auf Objekte und Komonaden beziehen?
scala
haskell
functional-programming
category-theory
recursion-schemes
fehlender Faktor
quelle
quelle
Antworten:
Algebren
Ich denke, der Ausgangspunkt wäre, die Idee einer Algebra zu verstehen . Dies ist nur eine Verallgemeinerung algebraischer Strukturen wie Gruppen, Ringe, Monoide und so weiter. Meistens werden diese Dinge in Form von Sets vorgestellt, aber da wir unter Freunden sind, werde ich stattdessen über Haskell-Typen sprechen. (Ich kann jedoch nicht widerstehen, einige griechische Buchstaben zu verwenden - sie lassen alles cooler aussehen!)
Eine Algebra ist also nur ein Typ
τ
mit einigen Funktionen und Identitäten. Diese Funktionen verwenden unterschiedlich viele Argumente vom Typτ
und erzeugen einτ
: ohne Eile sehen sie alle so aus(τ, τ,…, τ) → τ
. Sie können auch "Identitäten" haben - Elementeτ
davon haben bei einigen Funktionen ein besonderes Verhalten.Das einfachste Beispiel hierfür ist das Monoid. Ein Monoid ist jeder Typ
τ
mit einer Funktionmappend ∷ (τ, τ) → τ
und einer Identitätmzero ∷ τ
. Andere Beispiele sind Dinge wie Gruppen (die wie Monoide sind, außer mit einer zusätzlicheninvert ∷ τ → τ
Funktion), Ringe, Gitter und so weiter.Alle Funktionen arbeiten
τ
, können aber unterschiedliche Aritäten haben. Wir können diese alsτⁿ → τ
, woτⁿ
Karten zu einem Tupel von schreibenn
τ
. Auf diese Weise macht es Sinn , von Identitäten zu denken , wie ,τ⁰ → τ
woτ⁰
nur das leere Tupel ist()
. Wir können also die Idee einer Algebra jetzt tatsächlich vereinfachen: Es ist nur ein Typ mit einer Reihe von Funktionen.Eine Algebra ist nur ein gängiges Muster in der Mathematik, das "herausgerechnet" wurde, genau wie wir es mit Code tun. Die Leute bemerkten, dass eine ganze Reihe interessanter Dinge - die oben genannten Monoide, Gruppen, Gitter usw. - einem ähnlichen Muster folgen, also abstrahierten sie es. Dies hat den gleichen Vorteil wie beim Programmieren: Es erstellt wiederverwendbare Beweise und erleichtert bestimmte Arten des Denkens.
F-Algebren
Mit Factoring sind wir jedoch noch nicht ganz fertig. Bisher haben wir eine Reihe von Funktionen
τⁿ → τ
. Wir können tatsächlich einen ordentlichen Trick machen, um sie alle in einer Funktion zu kombinieren. Schauen wir uns insbesondere Monoide an: Wir habenmappend ∷ (τ, τ) → τ
undmempty ∷ () → τ
. Wir können diese mit einem Summentyp in eine einzige Funktion umwandelnEither
. Es würde so aussehen:Wir können tatsächlich diese Transformation verwenden immer wieder zu vereinen alle die
τⁿ → τ
Funktionen in einer einzigen, für jede Algebra. (In der Tat können wir dies für eine beliebige Anzahl von Funktionen tuna → τ
,b → τ
und so weiter für jedea, b,…
.)Dies lässt uns über Algebren als einen Typ
τ
mit einer einzelnen Funktion sprechen, von einem Durcheinander vonEither
s bis zu einer einzelnenτ
. Für Monoide ist dieses Durcheinander :Either (τ, τ) ()
; Für Gruppen (die eine zusätzlicheτ → τ
Operation haben) ist es :Either (Either (τ, τ) τ) ()
. Es ist ein anderer Typ für jede andere Struktur. Was haben all diese Typen gemeinsam? Das offensichtlichste ist, dass sie alle nur Summen von Produkten sind - algebraische Datentypen. Für Monoide könnten wir beispielsweise einen Monoid-Argumenttyp erstellen, der für jedes Monoid τ funktioniert :Wir können dasselbe für Gruppen, Ringe und Gitter und alle anderen möglichen Strukturen tun.
Was ist das Besondere an all diesen Typen? Nun, sie sind alle
Functors
! Z.B:So können wir unsere Vorstellung von einer Algebra noch weiter verallgemeinern. Es ist nur ein Typ
τ
mit einer Funktionf τ → τ
für einen Funktorf
. Tatsächlich könnten wir dies als Typklasse aufschreiben:Dies wird oft als "F-Algebra" bezeichnet, da sie vom Funktor bestimmt wird
F
. Wenn wir teilweise Typklassen anwenden könnten, könnten wir so etwas definierenclass Monoid = Algebra MonoidArgument
.Kohlegebren
Hoffentlich haben Sie jetzt einen guten Überblick darüber, was eine Algebra ist und wie sie nur eine Verallgemeinerung normaler algebraischer Strukturen ist. Was ist eine F-Kohlegebra? Nun, die Co impliziert, dass es das "Dual" einer Algebra ist - das heißt, wir nehmen eine Algebra und drehen einige Pfeile um. Ich sehe nur einen Pfeil in der obigen Definition, also drehe ich das einfach um:
Und das ist alles was es ist! Nun mag diese Schlussfolgerung ein wenig flippig erscheinen (heh). Es sagt Ihnen, was eine Kohlegebra ist, gibt aber keinen wirklichen Einblick darüber, wie nützlich es ist oder warum es uns wichtig ist. Ich werde gleich darauf zurückkommen, sobald ich ein oder zwei gute Beispiele gefunden oder gefunden habe: P.
Klassen und Objekte
Nachdem ich ein bisschen herumgelesen habe, denke ich, dass ich eine gute Vorstellung davon habe, wie man Kohlegebren verwendet, um Klassen und Objekte darzustellen. Wir haben einen Typ
C
, der alle möglichen internen Zustände von Objekten in der Klasse enthält. Die Klasse selbst ist eine Kohlegebra, überC
die die Methoden und Eigenschaften der Objekte angegeben werden.Wie im Algebra-Beispiel gezeigt, können wir, wenn wir eine Reihe von Funktionen wie
a → τ
undb → τ
für jede habena, b,…
, diese alle unter VerwendungEither
eines Summentyps zu einer einzigen Funktion kombinieren . Der duale „Begriff“ würde eine Reihe von Funktionen des Typs wird kombiniertτ → a
,τ → b
und so weiter. Wir können dies mit dem Dual eines Summentyps tun - einem Produkttyp. Angesichts der beiden oben genannten Funktionen (aufgerufenf
undg
) können wir also eine einzige wie folgt erstellen:Der Typ
(a, a)
ist auf einfache Weise ein Funktor, daher passt er sicherlich zu unserer Vorstellung einer F-Kohlegebra. Mit diesem speziellen Trick können wir eine Reihe verschiedener Funktionen - oder für OOP Methoden - in einer einzigen Funktion vom Typ zusammenfassenτ → f τ
.Die Elemente unseres Typs
C
repräsentieren den internen Zustand des Objekts. Wenn das Objekt einige lesbare Eigenschaften hat, müssen sie vom Status abhängig sein können. Der naheliegendste Weg, dies zu tun, besteht darin, sie zu einer Funktion von zu machenC
. Wenn wir also eine Längeneigenschaft wollen (z. B.object.length
), hätten wir eine FunktionC → Int
.Wir wollen Methoden, die ein Argument annehmen und den Status ändern können. Dazu müssen wir alle Argumente aufgreifen und ein neues erstellen
C
. Stellen wir uns einesetPosition
Methode vor, die einex
und einey
Koordinate nimmt :object.setPosition(1, 2)
. Es würde so aussehen :C → ((Int, Int) → C)
.Das wichtige Muster hierbei ist, dass die "Methoden" und "Eigenschaften" des Objekts das Objekt selbst als erstes Argument verwenden. Dies ist genau wie der
self
Parameter in Python und wie das Implizitthis
vieler anderer Sprachen. Eine Kohlegebra kapselt im Wesentlichen nur das Verhalten der Aufnahme einesself
Parameters: Das ist der ersteC
inC → F C
.Also lasst uns alles zusammenfügen. Stellen wir uns eine Klasse mit einer
position
Eigenschaft, einername
Eigenschaft und einersetPosition
Funktion vor:Wir brauchen zwei Teile, um diese Klasse darzustellen. Zunächst müssen wir den internen Zustand des Objekts darstellen. in diesem Fall hält es nur zwei
Int
s und aString
. (Dies ist unser TypC
.) Dann müssen wir uns die Kohlegebra einfallen lassen, die die Klasse darstellt.Wir haben zwei Eigenschaften zu schreiben. Sie sind ziemlich trivial:
Jetzt müssen wir nur noch die Position aktualisieren können:
Dies ist wie eine Python-Klasse mit ihren expliziten
self
Variablen. Jetzt, da wir eine Reihe vonself →
Funktionen haben, müssen wir sie zu einer einzigen Funktion für die Kohlegebra kombinieren. Wir können dies mit einem einfachen Tupel tun:Der Typ
((Int, Int), String, (Int, Int) → c)
- für jedenc
- ist ein Funktor undcoop
hat daher die gewünschte Form :Functor f ⇒ C → f C
.Vor diesem Hintergrund
C
zusammen mitcoop
einer Kohlegebra, die die Klasse angibt, die ich oben angegeben habe. Sie können sehen, wie wir dieselbe Technik verwenden können, um eine beliebige Anzahl von Methoden und Eigenschaften für unsere Objekte anzugeben.Auf diese Weise können wir kohlegebraisches Denken verwenden, um mit Klassen umzugehen. Zum Beispiel können wir den Begriff eines "F-Kohlegebra-Homomorphismus" einbringen, um Transformationen zwischen Klassen darzustellen. Dies ist ein beängstigend klingender Begriff, der nur eine Transformation zwischen Kohlegebren bedeutet, die die Struktur bewahrt. Dies erleichtert das Zuordnen von Klassen zu anderen Klassen erheblich.
Kurz gesagt, eine F-Kohlegebra stellt eine Klasse dar, indem sie eine Reihe von Eigenschaften und Methoden aufweist, die alle von einem
self
Parameter abhängen , der den internen Zustand jedes Objekts enthält.Andere Kategorien
Bisher haben wir über Algebren und Kohlegebren als Haskell-Typen gesprochen. Eine Algebra ist nur ein Typ
τ
mit einer Funktionf τ → τ
und eine Kohlegebra ist nur ein Typτ
mit einer Funktionτ → f τ
.Nichts verbindet diese Ideen jedoch wirklich mit Haskell an sich . Tatsächlich werden sie normalerweise eher in Form von Mengen und mathematischen Funktionen als in Form von Typen und Haskell-Funktionen eingeführt. In der Tat können wir diese Konzepte auf beliebige Kategorien verallgemeinern !
Wir können eine F-Algebra für eine Kategorie definieren
C
. Erstens brauchen wir einen FunktorF : C → C
- das heißt einen Endofunktor . (Alle HaskellFunctor
s sind eigentlich endofunctors ausHask → Hask
.) Dann wird eine Algebra ist nur ein ObjektA
ausC
mit einem MorphismusF A → A
. Eine Kohlegebra ist die gleiche außer mitA → F A
.Was gewinnen wir, wenn wir andere Kategorien berücksichtigen? Nun, wir können dieselben Ideen in verschiedenen Kontexten verwenden. Wie Monaden. In Haskell ist eine Monade ein Typ
M ∷ ★ → ★
mit drei Operationen:Die
map
Funktion ist nur ein Beweis dafür, dassM
aFunctor
. Wir können also sagen, dass eine Monade nur ein Funktor mit zwei Operationen ist:return
undjoin
.Funktoren bilden selbst eine Kategorie, wobei Morphismen zwischen ihnen sogenannte "natürliche Transformationen" sind. Eine natürliche Transformation ist nur eine Möglichkeit, einen Funktor in einen anderen zu verwandeln und dabei seine Struktur zu erhalten. Hier ist ein schöner Artikel, der die Idee erklärt. Es spricht darüber
concat
, was nurjoin
für Listen ist.Bei Haskell-Funktoren ist die Zusammensetzung von zwei Funktoren selbst ein Funktor. Im Pseudocode könnten wir Folgendes schreiben:
Dies hilft uns,
join
als Mapping von zu denkenf ∘ f → f
. Die Art vonjoin
ist∀α. f (f α) → f α
. Intuitiv können wir sehen, wie eine für alle Typen gültige Funktionα
als Transformation von betrachtet werden kannf
.return
ist eine ähnliche Transformation. Sein Typ ist∀α. α → f α
. Das sieht anders aus - der ersteα
ist nicht "in" einem Funktor! Glücklicherweise können wir dies beheben, indem wir dort einen Identitätsfunktor hinzufügen :∀α. Identity α → f α
. Soreturn
ist eine TransformationIdentity → f
.Jetzt können wir uns eine Monade als eine Algebra vorstellen, die auf einem Funktor
f
mit Operationenf ∘ f → f
und basiertIdentity → f
. Kommt Ihnen das nicht bekannt vor? Es ist sehr ähnlich zu einem Monoid, das nur eine Artτ
mit Operationenτ × τ → τ
und war() → τ
.Eine Monade ist also wie ein Monoid, nur dass wir anstelle eines Typs einen Funktor haben. Es ist die gleiche Art von Algebra, nur in einer anderen Kategorie. (Hier kommt, soweit ich weiß, der Satz "Eine Monade ist nur ein Monoid in der Kategorie der Endofunktoren" her.)
Jetzt haben wir diese beiden Operationen:
f ∘ f → f
undIdentity → f
. Um die entsprechende Kohlegebra zu erhalten, drehen wir einfach die Pfeile. Dies gibt uns zwei neue Operationen:f → f ∘ f
undf → Identity
. Wir können sie in Haskell-Typen umwandeln, indem wir wie oben Typvariablen hinzufügen und uns∀α. f α → f (f α)
und geben∀α. f α → α
. Dies sieht genauso aus wie die Definition einer Comonade:Eine Comonade ist also eine Kohlegebra in einer Kategorie von Endofunktoren.
quelle
(,)
dem Identitätsfunktor entspricht()
. Ein Monoidobjekt innerhalb einer Monoidkategorie ist ein Objekt mit Pfeilen, die Ihrer Monoidalgebra entsprechen und ein Monoidobjekt in Hask mit Produkttypen als Monoidstruktur beschreiben. Ein monoides Objekt in der Kategorie der Endofunktoren auf C ist eine Monade auf C, also ja, Ihr Verständnis ist korrekt. :]F-Algebren und F-Kohlegebren sind mathematische Strukturen, die beim Denken über induktive Typen (oder rekursive Typen ) eine wichtige Rolle spielen .
F-Algebren
Wir beginnen zuerst mit F-Algebren. Ich werde versuchen, so einfach wie möglich zu sein.
Ich denke, Sie wissen, was ein rekursiver Typ ist. Dies ist beispielsweise ein Typ für eine Liste von Ganzzahlen:
Es ist offensichtlich, dass es rekursiv ist - tatsächlich bezieht sich seine Definition auf sich selbst. Seine Definition besteht aus zwei Datenkonstruktoren, die die folgenden Typen haben:
Beachten Sie, dass ich Art geschrieben von
Nil
als() -> IntList
nicht einfachIntList
. Dies sind in der Tat aus theoretischer Sicht äquivalente Typen, da der()
Typ nur einen Einwohner hat.Wenn wir Signaturen dieser Funktionen satztheoretischer schreiben, erhalten wir
Dabei
1
handelt es sich um eine Einheitensatz (Satz mit einem Element) und dieA × B
Operation ist ein Kreuzprodukt aus zwei SätzenA
undB
(dh einem Satz von Paaren, bei(a, b)
denena
alle Elemente vonA
undb
alle Elemente von durchlaufen werdenB
).Disjunkte Vereinigung von zwei Mengen
A
undB
ist eine Menge,A | B
die eine Vereinigung von Mengen{(a, 1) : a in A}
und ist{(b, 2) : b in B}
. Im Wesentlichen handelt es sich um eine Menge aller Elemente aus beidenA
undB
, wobei jedoch jedes dieser Elemente als zu einemA
oder gekennzeichnetB
ist. Wenn wir also ein Element aus auswählen,A | B
wissen wir sofort, ob dieses Element vonA
oder von stammtB
.Wir können 'verbinden'
Nil
undCons
Funktionen, so dass sie eine einzige Funktion bilden, die an einer Menge arbeitet1 | (Int × IntList)
:Wenn die
Nil|Cons
Funktion auf den()
Wert angewendet wird (der offensichtlich zur1 | (Int × IntList)
Menge gehört), verhält sie sich tatsächlich so, als ob sie es wäreNil
. WennNil|Cons
es auf einen Wert vom Typ angewendet wird(Int, IntList)
(solche Werte sind auch in der Menge enthalten1 | (Int × IntList)
, verhält es sich wie folgt)Cons
.Betrachten Sie nun einen anderen Datentyp:
Es hat die folgenden Konstruktoren:
die auch zu einer Funktion verbunden werden kann:
Es ist ersichtlich, dass beide
joined
Funktionen einen ähnlichen Typ haben: Sie sehen beide so ausWo
F
ist eine Art von Transformation, die unseren Typ nimmt und einen komplexeren Typ ergibt, der ausx
und|
Operationen, VerwendungenT
und möglicherweise anderen Typen besteht. Zum Beispiel fürIntList
undIntTree
F
sieht wie folgt aus:Wir können sofort feststellen, dass jeder algebraische Typ auf diese Weise geschrieben werden kann. In der Tat werden sie deshalb als "algebraisch" bezeichnet: Sie bestehen aus einer Reihe von "Summen" (Gewerkschaften) und "Produkten" (Kreuzprodukten) anderer Typen.
Jetzt können wir die F-Algebra definieren. F-Algebra ist nur ein Paar
(T, f)
, wobeiT
es sich um einen Typ handelt undf
eine Funktion des Typs istf :: F T -> T
. In unseren Beispielen sind F-Algebren(IntList, Nil|Cons)
und(IntTree, Leaf|Branch)
. Beachten Sie jedoch, dass trotz dieser Art vonf
Funktion für jedes F die gleiche istT
undf
selbst beliebig sein kann. Zum Beispiel(String, g :: 1 | (Int x String) -> String)
oder(Double, h :: Int | (Double, Double) -> Double)
für einigeg
undh
sind auch F-Algebren für entsprechende F.Anschließend können wir F-Algebra-Homomorphismen und dann anfängliche F-Algebren einführen , die sehr nützliche Eigenschaften haben. In der Tat
(IntList, Nil|Cons)
ist eine anfängliche F1-Algebra und(IntTree, Leaf|Branch)
ist eine anfängliche F2-Algebra. Ich werde keine genauen Definitionen dieser Begriffe und Eigenschaften präsentieren, da sie komplexer und abstrakter als nötig sind.Die Tatsache, dass es sich beispielsweise
(IntList, Nil|Cons)
um eine F-Algebra handelt, ermöglicht es uns jedoch, einefold
ähnliche Funktion für diesen Typ zu definieren . Wie Sie wissen, ist fold eine Art Operation, die einen rekursiven Datentyp in einen endlichen Wert umwandelt. Zum Beispiel können wir eine Liste von Ganzzahlen in einen einzelnen Wert falten, der eine Summe aller Elemente in der Liste ist:Es ist möglich, eine solche Operation auf einen beliebigen rekursiven Datentyp zu verallgemeinern.
Das Folgende ist eine Signatur der
foldr
Funktion:Beachten Sie, dass ich geschweifte Klammern verwendet habe, um die ersten beiden Argumente vom letzten zu trennen. Dies ist keine echte
foldr
Funktion, aber sie ist isomorph dazu (das heißt, Sie können leicht eine von der anderen erhalten und umgekehrt). Teilweise angewendetfoldr
hat die folgende Unterschrift:Wir können sehen, dass dies eine Funktion ist, die eine Liste von Ganzzahlen verwendet und eine einzelne Ganzzahl zurückgibt. Definieren wir eine solche Funktion anhand unseres
IntList
Typs.Wir sehen, dass diese Funktion aus zwei Teilen besteht: Der erste Teil definiert das Verhalten dieser Funktion zum
Nil
TeilIntList
und der zweite Teil definiert das Verhalten der Funktion zumCons
Teil.Nehmen wir nun an, wir programmieren nicht in Haskell, sondern in einer Sprache, die die Verwendung algebraischer Typen direkt in Typensignaturen ermöglicht (technisch gesehen erlaubt Haskell die Verwendung algebraischer Typen über Tupel und
Either a b
Datentypen, dies führt jedoch zu unnötiger Ausführlichkeit). Betrachten Sie eine Funktion:Es ist zu sehen, dass dies
reductor
eine Funktion des Typs istF1 Int -> Int
, genau wie bei der Definition der F-Algebra! In der Tat ist das Paar(Int, reductor)
eine F1-Algebra.Da
IntList
ein anfänglicher F1-Algebra, für jeden TypT
und für jede Funktionr :: F1 T -> T
es eine Funktion gibt, genannt catamorphism fürr
, das umwandeltIntList
aufT
, und eine solche Funktion ist einzigartig. Denn in unserem Beispiel ein catamorphism fürreductor
istsumFold
. Beachten Sie, wiereductor
undsumFold
ähnlich sind: Sie haben fast die gleiche Struktur! In derreductor
Definition entspricht die Verwendung vons
Parametern (deren Typ entsprichtT
) der Verwendung des Ergebnisses der Berechnung vonsumFold xs
insumFold
Definition.Um es klarer zu machen und Ihnen zu helfen, das Muster zu sehen, hier ein weiteres Beispiel, und wir beginnen erneut mit der resultierenden Faltfunktion. Betrachten Sie die
append
Funktion, die ihr erstes Argument an das zweite anfügt:So sieht es auf unserer
IntList
:Versuchen wir noch einmal, den Reduktor aufzuschreiben:
appendFold
ist ein catamorphism fürappendReductor
welche transformiertIntList
inIntList
.Mit F-Algebren können wir also im Wesentlichen 'Falten' für rekursive Datenstrukturen definieren, dh Operationen, die unsere Strukturen auf einen gewissen Wert reduzieren.
F-Kohlegebren
F-Kohlegebren sind sogenannte "duale" Begriffe für F-Algebren. Sie ermöglichen es uns,
unfolds
für rekursive Datentypen eine Möglichkeit zu definieren, rekursive Strukturen aus einem bestimmten Wert zu konstruieren.Angenommen, Sie haben den folgenden Typ:
Dies ist ein unendlicher Strom von ganzen Zahlen. Sein einziger Konstruktor hat den folgenden Typ:
Oder in Form von Sets
Mit Haskell können Sie Musterübereinstimmungen für Datenkonstruktoren erstellen, sodass Sie die folgenden Funktionen definieren können, die an
IntStream
s arbeiten:Sie können diese Funktionen natürlich zu einer einzigen Funktion des Typs zusammenfügen
IntStream -> Int × IntStream
:Beachten Sie, wie das Ergebnis der Funktion mit der algebraischen Darstellung unseres
IntStream
Typs übereinstimmt . Ähnliches kann auch für andere rekursive Datentypen durchgeführt werden. Vielleicht haben Sie das Muster bereits bemerkt. Ich beziehe mich auf eine Familie von Funktionen des TypsWo
T
ist ein Typ? Von nun an werden wir definierenNun ist F-Kohlegebra ein Paar
(T, g)
, wobeiT
es sich um einen Typ undg
eine Funktion des Typs handeltg :: T -> F T
. Zum Beispiel(IntStream, head&tail)
ist eine F1-Kohlegebra. Auch hier, wie in F-Algebren,g
undT
willkürlich kann zum Beispiel(String, h :: String -> Int x String)
auch ein F1-Koalgebra für einige Stunden.Unter allen F-Kohlegebren gibt es sogenannte terminale F-Kohlegebren , die zu anfänglichen F-Algebren dual sind. Zum Beispiel
IntStream
ist eine terminale F-Kohlegebra. Dies bedeutet , dass für jeden TypT
und für jede Funktionp :: T -> F1 T
es eine Funktion gibt, genannt Anamorphismus , das umwandeltT
aufIntStream
, und eine solche Funktion ist einzigartig.Betrachten Sie die folgende Funktion, die ausgehend von der angegebenen einen Strom aufeinanderfolgender Ganzzahlen generiert:
Lassen Sie uns nun eine Funktion untersuchen
natsBuilder :: Int -> F1 Int
, dhnatsBuilder :: Int -> Int × Int
:Wieder können wir eine gewisse Ähnlichkeit zwischen
nats
und sehennatsBuilder
. Es ist sehr ähnlich zu der Verbindung, die wir zuvor mit Reduktoren und Falten beobachtet haben.nats
ist ein Anamorphismus fürnatsBuilder
.Ein weiteres Beispiel ist eine Funktion, die einen Wert und eine Funktion annimmt und einen Strom aufeinanderfolgender Anwendungen der Funktion auf den Wert zurückgibt:
Die Builder-Funktion ist die folgende:
Dann
iterate
ist ein Anamorphismus füriterateBuilder
.Fazit
Kurz gesagt, F-Algebren ermöglichen es, Falten zu definieren, dh Operationen, die die rekursive Struktur auf einen einzigen Wert reduzieren, und F-Kohlegebren ermöglichen das Gegenteil: Konstruieren Sie eine [potenziell] unendliche Struktur aus einem einzigen Wert.
Tatsächlich fallen in Haskell F-Algebren und F-Kohlegebren zusammen. Dies ist eine sehr schöne Eigenschaft, die eine Folge des Vorhandenseins eines "unteren" Werts in jedem Typ ist. In Haskell können also für jeden rekursiven Typ sowohl Falten als auch Entfaltungen erstellt werden. Das theoretische Modell dahinter ist jedoch komplexer als das oben vorgestellte, weshalb ich es bewusst vermieden habe.
Hoffe das hilft.
quelle
appendReductor
sieht etwas seltsam aus und hat mir nicht wirklich geholfen, das Muster dort zu erkennen ... :) Können Sie noch einmal überprüfen, ob es korrekt ist? .. Wie sollten Reduktortypen im Allgemeinen aussehen? Wird in der Definition vonr
dortF1
durch die IntList bestimmt, oder ist es ein beliebiges F?Das Tutorial durcharbeiten Ein Tutorial zu (Co) Algebren und (Co) Induktion soll Ihnen einen Einblick in die Co-Algebra in der Informatik geben.
Unten finden Sie ein Zitat davon, um Sie zu überzeugen,
Vorspiel über Kategorietheorie. Die Kategorietheorie sollte in Theorie der Funktoren umbenannt werden. Als Kategorien muss man definieren, um Funktoren zu definieren. (Darüber hinaus sind Funktoren das, was man definieren muss, um natürliche Transformationen zu definieren.)
Was ist ein Funktor? Es ist eine Transformation von einem Satz zum anderen, die ihre Struktur bewahrt. (Für mehr Details gibt es viele gute Beschreibungen im Netz).
Was ist eine F-Algebra? Es ist die Algebra des Funktors. Es ist nur das Studium der universellen Angemessenheit des Funktors.
Wie kann es eine Verbindung zur Informatik sein? Das Programm kann als strukturierter Informationssatz angezeigt werden. Die Programmausführung entspricht der Änderung dieses strukturierten Informationssatzes. Es klingt gut, dass die Ausführung die Programmstruktur beibehalten sollte. Die Ausführung kann dann als Anwendung eines Funktors über diesen Informationssatz angesehen werden. (Derjenige, der das Programm definiert).
Warum F-Co-Algebra? Programme sind im Wesentlichen dual, da sie durch Informationen beschrieben werden und darauf reagieren. Dann können hauptsächlich die Informationen, aus denen das Programm besteht und die geändert werden, auf zwei Arten angezeigt werden.
Dann möchte ich an dieser Stelle sagen:
Während der Laufzeit eines Programms existieren Daten und Status nebeneinander und ergänzen sich gegenseitig. Sie sind dual.
quelle
Ich werde mit Dingen beginnen, die offensichtlich mit der Programmierung zu tun haben, und dann einige mathematische Dinge hinzufügen, um sie so konkret und bodenständig wie möglich zu halten.
Lassen Sie uns einige Informatiker zur Koinduktion zitieren…
http://www.cs.umd.edu/~micinski/posts/2012-09-04-on-understanding-coinduction.html
http://adam.chlipala.net/cpdt/html/Coinductive.html
http://www.alexandrasilva.org/#/talks.html
Beziehen des mathematischen Umgebungskontexts auf übliche Programmieraufgaben
Was ist "eine Algebra"?
Algebraische Strukturen sehen im Allgemeinen so aus:
Dies sollte wie Objekte mit 1. Eigenschaften und 2. Methoden klingen. Oder noch besser, es sollte wie Typensignaturen klingen.
Zu den mathematischen Standardbeispielen gehören Monoid ⊃ Gruppe ⊃ Vektorraum ⊃ "eine Algebra". Monoide sind wie Automaten: Folgen von Verben (z
f.g.h.h.nothing.f.g.f
. B. ). Eingit
Protokoll, das immer den Verlauf hinzufügt und ihn niemals löscht, ist ein Monoid, aber keine Gruppe. Wenn Sie Inverse hinzufügen (z. B. negative Zahlen, Brüche, Wurzeln, Löschen des akkumulierten Verlaufs, Aufbrechen eines zerbrochenen Spiegels), erhalten Sie eine Gruppe.Gruppen enthalten Dinge, die addiert oder subtrahiert werden können. Zum Beispiel können
Duration
s addiert werden. (AberDate
s kann nicht.) Die Dauer lebt in einem Vektorraum (nicht nur in einer Gruppe), da sie auch durch externe Zahlen skaliert werden kann. (Eine Typensignatur vonscaling :: (Number,Duration) → Duration
.)Algebren ⊂ Vektorräume können noch etwas anderes: Es gibt einige
m :: (T,T) → T
. Nennen Sie dies "Multiplikation" oder nicht, denn sobald Sie gehen, istIntegers
es weniger offensichtlich, was "Multiplikation" (oder "Exponentiation" ) sein sollte.(Aus diesem Grund achten die Menschen auf (kategorietheoretische) universelle Eigenschaften: um ihnen zu sagen, wie Multiplikation funktionieren soll oder sein soll :
)
Algebren → Coalgebren
Comultiplication ist einfacher auf eine Weise zu definieren, die sich nicht willkürlich anfühlt, als Multiplikation, da
T → (T,T)
Sie einfach dasselbe Element wiederholen können. ("diagonale Karte" - wie diagonale Matrizen / Operatoren in der Spektraltheorie)Counit ist normalerweise die Spur (Summe der diagonalen Einträge), obwohl wiederum wichtig ist, was Ihr Counit tut ;
trace
ist nur eine gute Antwort für Matrizen.Der Grund, einen dualen Raum im Allgemeinen zu betrachten, liegt darin, dass es einfacher ist, in diesem Raum zu denken. Zum Beispiel ist es manchmal einfacher, an einen normalen Vektor zu denken als an die Ebene, für die er normal ist, aber Sie können Ebenen (einschließlich Hyperebenen) mit Vektoren steuern (und jetzt spreche ich von dem bekannten geometrischen Vektor, wie in einem Raytracer). .
(Un) strukturierte Daten zähmen
Mathematiker modellieren möglicherweise etwas, das Spaß macht, wie TQFTs , während Programmierer damit zu kämpfen haben
+ :: (Date,Duration) → Date
),Paris
≠(+48.8567,+2.3508)
! Es ist eine Form, kein Punkt.),Wenn Informatiker über Kohlegebren sprechen, denken sie normalerweise an festgelegte Operationen wie das kartesische Produkt. Ich glaube, das meinen die Leute, wenn sie sagen: "Algebren sind Kohlegebren in Haskell". Aber in dem Maße , dass Programmierer wie komplexe Datentypen zu modellieren haben
Place
,Date/Time
undCustomer
-und diese Modelle wie die reale Welt aussehen so viel machen (oder zumindest die Endbenutzers Sicht der realen Welt) wie möglich, ich glaube duals, könnte über die Set-Welt hinaus nützlich sein.quelle