Im recursion-schemes
Paket sind folgende Typen definiert:
newtype Fix f = Fix (f (Fix f))
newtype Mu f = Mu (forall a. (f a -> a) -> a)
Sind sie isomorph? Wenn ja, wie beweisen Sie das?
Im recursion-schemes
Paket sind folgende Typen definiert:
newtype Fix f = Fix (f (Fix f))
newtype Mu f = Mu (forall a. (f a -> a) -> a)
Sind sie isomorph? Wenn ja, wie beweisen Sie das?
Mu f < Fix f < Nu f
Fix
-to-Mu
ist im Wesentlichencata
, währendMu
-to-Fix
istmu2fix (Mu x) = x Fix
. Der schwierige Teil besteht darin, zu beweisen, dass es sich um gegenseitige Umkehrungen handelt, bei denen die Parametrizität ausgenutzt wird.Fix
, der nicht durch dargestellt werden kannMu
? ISTMFix
sollte das kleinste sein (intuitiv, weil es eine "Datenstruktur" ist und keine Bottoms enthalten kann)Antworten:
Ja, sie sind in Haskell isomorph. Weitere Hinweise finden Sie unter Was ist der Unterschied zwischen Fix, Mu und Nu im Rekursionsschema-Paket von Ed Kmett .
Beginnen wir mit der Definition von Funktionen zur Durchführung der Konvertierungen:
Um zu zeigen, dass diese Funktionen einen Isomorphismus aufweisen, müssen wir Folgendes zeigen:
Von
Fix
und zurückEine der Richtungen des Isomorphismus ist etwas einfacher als die andere:
Die letzte Passage oben
cata Fix t = t
kann durch die Definition voncata
:cata Fix t
dann istFix (fmap (cata Fix) (unfix t))
. Wir können Induktion verwenden, um zu zeigen, dass est
zumindest für ein Endliches sein musst
(es wird subtiler mit unendlichen Strukturen - siehe den Anhang am Ende dieser Antwort). Es gibt zwei Möglichkeiten zu berücksichtigen:unfix t :: f (Fix f)
ist leer und hat keine rekursiven Positionen, in die man graben kann. In diesem Fall muss esfmap absurd z
für einige gleich seinz :: f Void
und somit:unfix t
ist nicht leer. In diesem Fall wissen wir zumindest, dassfmap (cata Fix)
wir nichts anderes tun können , als unscata Fix
auf die rekursiven Positionen zu bewerben . Die Induktionshypothese lautet hier, dass diese Positionen dadurch unverändert bleiben. Wir haben dann:(Letztendlich
cata Fix = id
ist dies eine FolgeFix :: f (Fix f) -> Fix x
einer anfänglichen F-Algebra. Ein direkter Rückgriff auf diese Tatsache im Zusammenhang mit diesem Beweis wäre wahrscheinlich eine zu große Abkürzung.)Von
Mu
und zurückGegeben
muToFix . fixToMu = id
, um zu beweisen, dassfixToMu . muToFix = id
es ausreicht, entweder zu beweisen:das
muToFix
ist injektiv oderdas
fixToMu
ist surjektiv.Nehmen wir die zweite Option und überprüfen Sie die relevanten Definitionen:
fixToMu
wobei surjektiv, dann bedeutet das, jede spezifische angegebenFunctor
f
, sind alle Funktionen des Typsforall a. (f a -> a) -> a
können wie folgt definiert werden\alg -> cata alg t
, für einige bestimmtet :: Fix f
. Die Aufgabe besteht dann darin, dieforall a. (f a -> a) -> a
Funktionen zu katalogisieren und zu prüfen, ob alle in dieser Form ausgedrückt werden können.Wie können wir eine
forall a. (f a -> a) -> a
Funktion definieren , ohne uns darauf zu stützenfixToMu
? Egal was passiert, es muss dief a -> a
Algebra als Argument verwendet werden, um eina
Ergebnis zu erhalten. Der direkte Weg würde es auf einen bestimmtenf a
Wert anwenden . Eine wichtige Einschränkung ist, dassa
wir , da es polymorph ist, in der Lage sein müssen, diesenf a
Wert für jede Wahl von zu beschwörena
. Das ist eine praktikable Strategie, solangef
Werte existieren. In diesem Fall können wir Folgendes tun:Um die Notation klarer zu machen, definieren wir einen Typ für Dinge, mit denen wir
forall a. (f a -> a) -> a
Funktionen definieren können:Neben dem direkten Weg gibt es nur eine weitere Möglichkeit. Da
f
ist eineFunctor
, wenn wir irgendwie einen habenf (Moo f)
Wert , den wir zweimal die Algebra anwenden können, die erste Anwendung unter der äußeren wobeif
Schicht überfmap
undfromMoo
:In Anbetracht dessen, dass wir auch
forall a. (f a -> a) -> a
ausf (Moo f)
Werten machen können, ist es sinnvoll, sie als Fall hinzuzufügenMoo
:Dementsprechend
fromLayered
kann eingearbeitet werden zufromMoo
:Beachten Sie, dass wir auf diese Weise von der Anwendung
alg
unter einerf
Ebene zur rekursiven Anwendungalg
unter einer beliebigen Anzahl vonf
Ebenen übergegangen sind.Als nächstes können wir feststellen, dass ein
f Void
Wert in denLayered
Konstruktor eingefügt werden kann :Das heißt, wir brauchen den
Empty
Konstruktor eigentlich nicht :Was ist mit dem
Empty
Fall infromMoo
? Der einzige Unterschied zwischen den beiden Fällen besteht darin, dassEmpty
wir in dem Fallabsurd
statt haben\moo -> fromMoo moo alg
. Da alleVoid -> a
Funktionen vorhanden sindabsurd
, benötigen wir dort auch keinen separatenEmpty
Fall:Eine mögliche kosmetische Optimierung ist das Umdrehen der
fromMoo
Argumente, sodass wir das Argument nichtfmap
als Lambda schreiben müssen :Oder punktfreier:
An dieser Stelle deutet ein zweiter Blick auf unsere Definitionen darauf hin, dass eine Umbenennung angebracht ist:
Und da ist es: Alle
forall a. (f a -> a) -> a
Funktionen haben\alg -> cata alg t
für einige die Formt :: Fix f
. DaherfixToMu
ist surjektiv, und wir haben den gewünschten Isomorphismus.Nachtrag
In den Kommentaren wurde eine deutsche Frage nach der Anwendbarkeit des Induktionsarguments in der
cata Fix t = t
Ableitung aufgeworfen . Zumindest stellen die Funktorgesetze und die Parametrizität sicher, dassfmap (cata Fix)
keine zusätzliche Arbeit entsteht (zum Beispiel wird die Struktur nicht vergrößert oder es werden zusätzliche rekursive Positionen zum Eingraben eingeführt), was rechtfertigt, warum das Betreten der rekursiven Positionen alles ist zählt im induktiven Schritt der Ableitung. Wennt
es sich also um eine endliche Struktur handelt, wird der Grundfall eines leerenf (Fix t)
schließlich erreicht, und alles ist klar. Wenn wir jedoch zulassent
, dass wir unendlich sind, können wirfmap
nach undfmap
nach endlos weiter absteigenfmap
, ohne jemals den Basisfall zu erreichen.Die Situation mit unendlichen Strukturen ist jedoch nicht so schrecklich, wie es zunächst scheinen mag. Faulheit, die unendliche Strukturen überhaupt lebensfähig macht, ermöglicht es uns, unendliche Strukturen träge zu konsumieren:
Während sich die Abfolge rekursiver Positionen unendlich erstreckt, können wir an jedem Punkt anhalten und nützliche Ergebnisse aus den umgebenden Funktionskontexten
ListF
erzielen. Solche Kontexte, so wiederholt sich, sind davon nicht betroffenfmap
, und daher wird jedes endliche Segment der Struktur, das wir möglicherweise konsumieren, davon nicht betroffen seincata Fix
.Diese Faulheit Begnadigung spiegelt wider , wie, wie an anderer Stelle in dieser Diskussion erwähnt, Faulheit kollabiert die Unterscheidung zwischen den Fixpunkten
Mu
,Fix
undNu
. Ohne Faulheit reichtFix
es nicht aus, die produktive Kernkursion zu kodieren, und deshalb müssen wir zumNu
größten Fixpunkt wechseln . Hier ist eine winzige Demonstration des Unterschieds:quelle
cata Fix t = t
? Angenommen,Fix f
die anfängliche Algebra fürf
scheint eine Abkürzung zu sein. (Der aus der entsprechenden Antwort verknüpfte Beweis scheint dies zu umgehen, indem Parametrizität in beide Richtungen verwendet wird.)fixToMu
Surjektivität nicht. "wenn wir ein forall a definieren wollen. (fa -> a) -> eine Funktion von Grund auf neu" Das wollen wir nicht. Lassen Siek :: forall a. (f a -> a) -> a
uns stattdessen dask = \alg -> cata alg t
für einige zeigent
.cata Fix
haben wircata Fix = Fix . fmap (cata Fix) . unfix
. Wennt
keine rekursiven Positionen vorhanden sind,fmap (cata Fix)
wird nichts unternommen, und so weitercata Fix t = Fix (unfix t) = t
. Wenn es rekursive Positionen hat,fmap (cata Fix)
wird es nurcata Fix
auf sie angewendet , was ausreicht, um die Angelegenheit durch Induktion zu regeln.k
entweder durch direktes Anwenden der Algebra (für die einf Void
Wert benötigt wird) oder durchfmap
rekursives Anwenden verwendet werden muss, und beide Fälle können in der Form \ alg -> cata alg t` ausgedrückt werden. Ich glaube, ich habe getan, was Sie vorschlagen, obwohl "von Grund auf" möglicherweise nicht die beste Wortwahl war, um es zu beschreiben.cata Fix t = t
Ableitung hinzugefügt (angesichts der Ähnlichkeiten zwischen den beiden Argumenten ist es meiner Meinung nach jetzt hilfreich, den Grundstein für den zweiten Teil der Antwort zu legen). . Vielen Dank, dass Sie diese Stellen zur Verbesserung hervorgehoben haben.