Kurze Frage: Welche Bedeutung haben isomorphe Funktionen bei der Programmierung (nämlich bei der funktionalen Programmierung)?
Lange Frage: Ich versuche, einige Analoga zwischen funktionaler Programmierung und Konzepten in der Kategorietheorie zu ziehen, die auf einem Teil der Umgangssprache basieren, die ich von Zeit zu Zeit höre. Im Wesentlichen versuche ich, diesen Jargon in etwas Konkretes "auszupacken", das ich dann erweitern kann. Ich werde dann in der Lage sein, den Jargon mit einem Verständnis dafür zu verwenden, wovon zum Teufel ich spreche. Welches ist immer schön.
Einer dieser Begriffe, den ich ständig höre, ist Isomorphismus . Ich nehme an, es geht darum, über die Äquivalenz zwischen Funktionen oder Funktionszusammensetzungen nachzudenken. Ich habe mich gefragt, ob jemand einige Einblicke in einige gängige Muster geben könnte, bei denen die Eigenschaft des Isomorphismus nützlich ist (bei der funktionalen Programmierung), und für alle gewonnenen Nebenprodukte, wie z. B. Compiler-Optimierungen aus Überlegungen zu isomorphen Funktionen.
iso-
bedeutet gleich (/ äquivalent): en.wiktionary.org/wiki/iso-#Etymology und-morph-
bedeutet Form / Form: thefreedictionary.com/morph . Ein Isomorphismus ist also die Beziehung / Funktion der Äquivalenz zwischen zwei Typen. Wie man einen definieren kann, wird im Folgenden bereits sehr, sehr gut erklärt.Antworten:
Ich habe ein kleines Problem mit der positiv bewerteten Antwort für Isomorphismus, da die kategorietheoretische Definition von Isomorphismus nichts über Objekte aussagt. Um zu sehen, warum, überprüfen wir die Definition.
Definition
Ein Isomorphismus ist ein Paar von Morphismen (dh Funktionen),
f
und zwarg
so, dass:Diese Morphismen werden dann "Iso" -Morphismen genannt. Viele Leute verstehen nicht, dass sich der "Morphismus" im Isomorphismus auf die Funktion und nicht auf das Objekt bezieht. Sie würden jedoch sagen, dass die Objekte, die sie verbinden, "isomorph" sind, was die andere Antwort beschreibt.
Beachten Sie, dass die Definition des Isomorphismus nicht sagt, was (
.
)id
oder sein=
muss. Die einzige Voraussetzung ist, dass sie, was auch immer sie sind, auch die Kategoriengesetze erfüllen:Die Zusammensetzung (dh (
.
)) verbindet zwei Morphismen zu einem Morphismus undid
bezeichnet eine Art "Identitäts" -Übergang. Das heißt, wenn sich unsere Isomorphismen zum Identitätsmorphismus aufheben,id
können Sie sie als Umkehrungen voneinander betrachten.Für den speziellen Fall, in dem die Morphismen Funktionen sind, wird dann
id
als Identitätsfunktion definiert:... und Zusammensetzung ist definiert als:
... und zwei Funktionen sind Isomorphismen, wenn sie sich beim Erstellen der Identitätsfunktion aufheben
id
.Morphismen gegen Objekte
Es gibt jedoch mehrere Möglichkeiten, wie zwei Objekte isomorph sein können. Zum Beispiel bei den folgenden zwei Typen:
Es gibt zwei Isomorphismen zwischen ihnen:
Deshalb ist es besser, den Isomorphismus anhand der spezifischen Funktionen zu beschreiben, die die beiden Objekte betreffen, als anhand der beiden Objekte, da es möglicherweise nicht unbedingt ein eindeutiges Funktionspaar zwischen zwei Objekten gibt, das die Isomorphismusgesetze erfüllt.
Beachten Sie außerdem, dass es nicht ausreicht, wenn die Funktionen invertierbar sind. Beispielsweise sind die folgenden Funktionspaare keine Isomorphismen:
Auch wenn beim Verfassen keine Informationen verloren
f1 . g2
gehen, kehren Sie nicht in Ihren ursprünglichen Zustand zurück, selbst wenn der endgültige Zustand denselben Typ hat.Außerdem müssen Isomorphismen nicht zwischen konkreten Datentypen liegen. Hier ist ein Beispiel für zwei kanonische Isomorphismen, die nicht zwischen konkreten algebraischen Datentypen liegen und stattdessen einfach Funktionen in Beziehung setzen:
curry
unduncurry
:Verwendung für Isomorphismen
Kodierung der Kirche
Eine Verwendung von Isomorphismen besteht darin, Datentypen als Funktionen in der Kirche zu kodieren. Zum Beispiel
Bool
ist isomorph zuforall a . a -> a -> a
:Überprüfen Sie das
f . g = id
undg . f = id
.Der Vorteil von Church-Codierungsdatentypen besteht darin, dass sie manchmal schneller ausgeführt werden (da Church-Codierung ein Continuation-Passing-Stil ist) und in Sprachen implementiert werden können, die überhaupt keine Sprachunterstützung für algebraische Datentypen bieten.
Implementierungen übersetzen
Manchmal versucht man, die Implementierung einer Funktion einer Bibliothek mit der Implementierung einer anderen Bibliothek zu vergleichen. Wenn Sie beweisen können, dass sie isomorph sind, können Sie beweisen, dass sie gleich leistungsfähig sind. Die Isomorphismen beschreiben auch, wie eine Bibliothek in die andere übersetzt wird.
Beispielsweise gibt es zwei Ansätze, mit denen eine Monade aus der Signatur eines Funktors definiert werden kann. Eine ist die freie Monade, die vom
free
Paket bereitgestellt wird , und die andere ist die operative Semantik, die vomoperational
Paket bereitgestellt wird .Wenn Sie sich die beiden Kerndatentypen ansehen, sehen sie unterschiedlich aus, insbesondere ihre zweiten Konstruktoren:
... aber sie sind tatsächlich isomorph! Das bedeutet, dass beide Ansätze gleich leistungsfähig sind und jeder in einem Ansatz geschriebene Code mithilfe der Isomorphismen mechanisch in den anderen Ansatz übersetzt werden kann.
Isomorphismen, die keine Funktionen sind
Isomorphismen sind auch nicht auf Funktionen beschränkt. Sie sind tatsächlich für jede definiert
Category
und Haskell hat viele Kategorien. Aus diesem Grund ist es sinnvoller, in Morphismen als in Datentypen zu denken.Beispielsweise bildet der
Lens
Typ (vondata-lens
) eine Kategorie, in der Sie Linsen zusammenstellen und eine Identitätslinse haben können. Mit unserem obigen Datentyp können wir also zwei Linsen definieren, die Isomorphismen sind:Beachten Sie, dass zwei Isomorphismen im Spiel sind. Einer ist der Isomorphismus, der zum Aufbau jeder Linse (dh
f1
undg1
) verwendet wird (und deshalb wird diese Konstruktionsfunktion auch genanntiso
), und dann sind die Linsen selbst auch Isomorphismen. Es ist zu beachten, dass in der obigen Formulierung die verwendete Zusammensetzung (.
) keine Funktionszusammensetzung, sondern eine Linsenzusammensetzung ist undid
nicht die Identitätsfunktion, sondern die Identitätslinse:Das heißt, wenn wir unsere beiden Linsen zusammensetzen, sollte das Ergebnis nicht von dieser Identitätslinse zu unterscheiden sein.
quelle
Program
und zu zeigenFree
; Ich kann es nicht auf einen Blick herausfinden.Program f
ist isomorph zuFree (Coyoneda f)
undCoyoneda f
isomorph zuf
, weshalb die beiden Typen isomorph sind. Ich habe es weggelassen, weil der Beweis etwas komplizierter ist.operational
, aber die Basismonade entfernt, um sie zu einer gewöhnlichen Monade anstelle eines Monadentransformators zu machen. Dabei habe ich vergessen, dasT
s aus den Konstruktoren zu entfernen , aber ich habe es behoben.Ein Isomorphismus
u :: a -> b
ist eine Funktion, die eine Umkehrung hat , dh eine andere Funktion,v :: b -> a
so dass die Beziehungensind zufrieden. Sie sagen, dass zwei Typen isomorph sind, wenn zwischen ihnen ein Isomorphismus besteht. Dies bedeutet im Wesentlichen, dass Sie sie als denselben Typ betrachten können - alles, was Sie mit dem einen tun können, können Sie mit dem anderen tun.
Isomorphismus von Funktionen
Die beiden Funktionstypen
sind isomorph, da wir schreiben können
Sie können das überprüfen
u . v
undv . u
sind beidesid
. In der Tat sind die Funktionenu
undv
besser unter den Namencurry
und bekanntuncurry
.Isomorphismus und Newtypes
Wir nutzen den Isomorphismus immer dann aus, wenn wir eine Newtype-Deklaration verwenden. Zum Beispiel ist der zugrunde liegende Typ der Staatsmonade
s -> (a,s)
, über den man etwas verwirrend nachdenken kann. Durch Verwendung einer Newtype-Deklaration:Wir erzeugen einen neuen Typ,
State s a
der isomorph ists -> (a,s)
und der deutlich macht, wenn wir ihn verwenden. Wir denken über Funktionen nach, die einen veränderbaren Zustand haben. Wir bekommen auch einen praktischen KonstruktorState
und einen GetterrunState
für den neuen Typ.Monaden und Comonaden
Eine erweiterte Sicht betrachtet der Isomorphismus mit
curry
unduncurry
dass ich oben verwendet. DerReader r a
Typ hat die newtype-DeklarationIm Zusammenhang mit Monaden hat eine Funktion
f
, die einen Leser erzeugt, daher die Typensignaturdas ist äquivalent zu
Das ist die Hälfte des Curry / Uncurry-Isomorphismus. Wir können auch den
CoReader r a
Typ definieren :was zu einer Comonade gemacht werden kann. Dort haben wir eine Funktion cobind oder
=>>
eine Funktion, die einen Coreader übernimmt und einen Rohtyp erzeugt:das ist isomorph zu
Aber wir haben das bereits gesehen
a -> r -> b
und(a,r) -> b
sind isomorph, was uns eine nicht triviale Tatsache gibt: Die Lesermonade (mit monadischer Bindung) und die Coreader-Comonade (mit comonadischer Kobinde) sind ebenfalls isomorph! Insbesondere können beide für den gleichen Zweck verwendet werden - die Bereitstellung einer globalen Umgebung, die durch jeden Funktionsaufruf geführt wird.quelle
Denken Sie in Datentypen. In Haskell können Sie sich beispielsweise zwei Datentypen als isomorph vorstellen, wenn zwei Funktionen vorhanden sind, die Daten auf einzigartige Weise zwischen ihnen transformieren. Die folgenden drei Typen sind isomorph zueinander:
Sie können sich die Funktionen, die sich zwischen ihnen transformieren, als Isomorphismen vorstellen. Dies passt zur kategorischen Idee des Isomorphismus. Wenn zwischen
Type1
und mitType2
zwei Funktionenf
undg
mit existierenf . g = g . f = id
, sind die beiden Funktionen Isomorphismen zwischen diesen beiden Typen (Objekten).quelle
f
undg
ist eine Bijektion.map
Sie auch Isomorphismen zwischen verschiedenen Arten von Listen erstellen. Gleiches gilt fürfmap
und für anwendbare Typen.x
?func = f . g
...func x