Fix und Mu isomorph

8

Im recursion-schemesPaket 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?

Marcosh
quelle
3
Relevant: Was ist der Unterschied zwischen Fix, Mu und Nu in Ed Kmetts Rekursionsschema-Paket (die Antwort, die es dort nicht gibt, ist der explizit aufgeschriebene Isomorphismus).
Duplode
In haskell wird ja (weil faul) in strenger Sprache seinMu f < Fix f < Nu f
xgrommx
2
@duplode Über die Isomorphismen; Fix-to- Muist im Wesentlichen cata, während Mu-to- Fixist mu2fix (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.
Chi
Sie können diese Kata auch lösen. Codewars.com/kata/folding-through-a-fixed-point
xgrommx
1
@xgrommx, was ist in einem strengen Kontext ein Beispiel für einen Begriff, der durch dargestellt werden kann Fix, der nicht durch dargestellt werden kann Mu? ISTM Fixsollte das kleinste sein (intuitiv, weil es eine "Datenstruktur" ist und keine Bottoms enthalten kann)
luqui

Antworten:

4

Sind sie isomorph?

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 .

Wenn ja, wie beweisen Sie das?

Beginnen wir mit der Definition von Funktionen zur Durchführung der Konvertierungen:

muToFix :: Mu f -> Fix f
muToFix (Mu s) = s Fix

fixToMu :: Functor f => Fix f -> Mu f
fixToMu t = Mu (\alg -> cata alg t)

Um zu zeigen, dass diese Funktionen einen Isomorphismus aufweisen, müssen wir Folgendes zeigen:

muToFix . fixToMu = id
fixToMu . muToFix = id

Von Fixund zurück

Eine der Richtungen des Isomorphismus ist etwas einfacher als die andere:

muToFix (fixToMu t) = t
muToFix (fixToMu t)  -- LHS
muToFix (Mu (\f -> cata f t))
(\f -> cata f t) Fix
cata Fix t  -- See below.
t  -- LHS = RHS

Die letzte Passage oben cata Fix t = tkann durch die Definition von cata:

cata :: Functor f => (f a -> a) -> Fix f -> a
cata alg = alg . fmap (cata alg) . unfix

cata Fix tdann ist Fix (fmap (cata Fix) (unfix t)). Wir können Induktion verwenden, um zu zeigen, dass es tzumindest für ein Endliches sein muss t(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 es fmap absurd zfür einige gleich sein z :: f Voidund somit:

    cata Fix t
    Fix (fmap (cata Fix) (unfix t))
    Fix (fmap (cata Fix) (fmap absurd z))
    Fix (fmap (cata Fix . absurd) z)
    -- fmap doesn't do anything on an empty structure.
    Fix (fmap absurd z)
    Fix (unfix t)
    t
  • unfix tist nicht leer. In diesem Fall wissen wir zumindest, dass fmap (cata Fix)wir nichts anderes tun können , als uns cata Fixauf die rekursiven Positionen zu bewerben . Die Induktionshypothese lautet hier, dass diese Positionen dadurch unverändert bleiben. Wir haben dann:

    cata Fix t
    Fix (fmap (cata Fix) (unfix t))
    Fix (unfix t)  -- Induction hypothesis.
    t

(Letztendlich cata Fix = idist dies eine Folge Fix :: f (Fix f) -> Fix xeiner 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 Muund zurück

Gegeben muToFix . fixToMu = id, um zu beweisen, dass fixToMu . muToFix = ides ausreicht, entweder zu beweisen:

  • das muToFixist injektiv oder

  • das fixToMuist surjektiv.

Nehmen wir die zweite Option und überprüfen Sie die relevanten Definitionen:

newtype Mu f = Mu (forall a. (f a -> a) -> a)

fixToMu :: Functor f => Fix f -> Mu f
fixToMu t = Mu (\alg -> cata alg t)

fixToMuwobei surjektiv, dann bedeutet das, jede spezifische angegeben Functor f, sind alle Funktionen des Typs forall a. (f a -> a) -> akönnen wie folgt definiert werden \alg -> cata alg t, für einige bestimmte t :: Fix f. Die Aufgabe besteht dann darin, die forall a. (f a -> a) -> aFunktionen 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) -> aFunktion definieren , ohne uns darauf zu stützen fixToMu? Egal was passiert, es muss die f a -> aAlgebra als Argument verwendet werden, um ein aErgebnis zu erhalten. Der direkte Weg würde es auf einen bestimmten f aWert anwenden . Eine wichtige Einschränkung ist, dass awir , da es polymorph ist, in der Lage sein müssen, diesen f aWert für jede Wahl von zu beschwören a. Das ist eine praktikable Strategie, solange fWerte existieren. In diesem Fall können wir Folgendes tun:

fromEmpty :: Functor f => f Void -> forall a. (f a -> a) -> a
fromEmpty z = \alg -> alg (fmap absurd z)

Um die Notation klarer zu machen, definieren wir einen Typ für Dinge, mit denen wir forall a. (f a -> a) -> aFunktionen definieren können:

data Moo f = Empty (f Void)

fromMoo :: Functor f => Moo f -> forall a. (f a -> a) -> a
fromMoo (Empty z) = \alg -> alg (fmap absurd z)

Neben dem direkten Weg gibt es nur eine weitere Möglichkeit. Da fist eine Functor, wenn wir irgendwie einen haben f (Moo f)Wert , den wir zweimal die Algebra anwenden können, die erste Anwendung unter der äußeren wobei fSchicht über fmapund fromMoo:

fromLayered :: Functor f => f (Moo f) -> forall a. (f a -> a) -> a
fromLayered u = \alg -> alg (fmap (\moo -> fromMoo moo alg) u)

In Anbetracht dessen, dass wir auch forall a. (f a -> a) -> aaus f (Moo f)Werten machen können, ist es sinnvoll, sie als Fall hinzuzufügen Moo:

data Moo f = Empty (f Void) | Layered (f (Moo f))

Dementsprechend fromLayeredkann eingearbeitet werden zu fromMoo:

fromMoo :: Functor f => Moo f -> forall a. (f a -> a) -> a
fromMoo = \case
    Empty z -> \alg -> alg (fmap absurd z)
    Layered u -> \alg -> alg (fmap (\moo -> fromMoo moo alg) u)

Beachten Sie, dass wir auf diese Weise von der Anwendung algunter einer fEbene zur rekursiven Anwendung algunter einer beliebigen Anzahl von fEbenen übergegangen sind.

Als nächstes können wir feststellen, dass ein f VoidWert in den LayeredKonstruktor eingefügt werden kann :

emptyLayered :: Functor f => f Void -> Moo f
emptyLayered z = Layered (fmap absurd z)

Das heißt, wir brauchen den EmptyKonstruktor eigentlich nicht :

newtype Moo f = Moo (f (Moo f))

unMoo :: Moo f -> f (Moo f)
unMoo (Moo u) = u

Was ist mit dem EmptyFall in fromMoo? Der einzige Unterschied zwischen den beiden Fällen besteht darin, dass Emptywir in dem Fall absurdstatt haben \moo -> fromMoo moo alg. Da alle Void -> aFunktionen vorhanden sind absurd, benötigen wir dort auch keinen separaten EmptyFall:

fromMoo :: Functor f => Moo f -> forall a. (f a -> a) -> a
fromMoo (Moo u) = \alg -> alg (fmap (\moo -> fromMoo moo alg) u)

Eine mögliche kosmetische Optimierung ist das Umdrehen der fromMooArgumente, sodass wir das Argument nicht fmapals Lambda schreiben müssen :

foldMoo :: Functor f => (f a -> a) -> Moo f -> a
foldMoo alg (Moo u) = alg (fmap (foldMoo alg) u)

Oder punktfreier:

foldMoo :: Functor f => (f a -> a) -> Moo f -> a
foldMoo alg = alg . fmap (foldMoo alg) . unMoo

An dieser Stelle deutet ein zweiter Blick auf unsere Definitionen darauf hin, dass eine Umbenennung angebracht ist:

newtype Fix f = Fix (f (Fix f))

unfix :: Fix f -> f (Fix f)
unfix (Fix u) = u

cata :: Functor f => (f a -> a) -> Fix f -> a
cata alg = alg . fmap (cata alg) . unfix

fromFix :: Functor f => Fix f -> forall a. (f a -> a) -> a
fromFix t = \alg -> cata alg t

Und da ist es: Alle forall a. (f a -> a) -> aFunktionen haben \alg -> cata alg tfür einige die Form t :: Fix f. Daher fixToMuist 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 = tAbleitung aufgeworfen . Zumindest stellen die Funktorgesetze und die Parametrizität sicher, dass fmap (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. Wenn tes sich also um eine endliche Struktur handelt, wird der Grundfall eines leeren f (Fix t)schließlich erreicht, und alles ist klar. Wenn wir jedoch zulassen t, dass wir unendlich sind, können wir fmapnach und fmapnach endlos weiter absteigen fmap, 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:

GHCi> :info ListF
data ListF a b = Nil | Cons a b
    -- etc.
GHCi> ones = Fix (Cons 1 ones)
GHCi> (\(Fix (Cons a _)) -> a) (cata Fix ones)
1
GHCi> (\(Fix (Cons _ (Fix (Cons a _)))) -> a) (cata Fix ones)
1

Während sich die Abfolge rekursiver Positionen unendlich erstreckt, können wir an jedem Punkt anhalten und nützliche Ergebnisse aus den umgebenden Funktionskontexten ListFerzielen. Solche Kontexte, so wiederholt sich, sind davon nicht betroffen fmap, und daher wird jedes endliche Segment der Struktur, das wir möglicherweise konsumieren, davon nicht betroffen sein cata Fix.

Diese Faulheit Begnadigung spiegelt wider , wie, wie an anderer Stelle in dieser Diskussion erwähnt, Faulheit kollabiert die Unterscheidung zwischen den Fixpunkten Mu, Fixund Nu. Ohne Faulheit reicht Fixes nicht aus, die produktive Kernkursion zu kodieren, und deshalb müssen wir zum Nugrößten Fixpunkt wechseln . Hier ist eine winzige Demonstration des Unterschieds:

GHCi> :set -XBangPatterns
GHCi> -- Like ListF, but strict in the recursive position.
GHCi> data SListF a b = SNil | SCons a !b deriving Functor
GHCi> ones = Nu (\() -> SCons 1 ()) ()
GHCi> (\(Nu c a) -> (\(SCons a _) -> a) (c a)) ones
1
GHCi> ones' = Fix (SCons 1 ones')
GHCi> (\(Fix (SCons a _)) -> a) ones'
^CInterrupted.
Duplode
quelle
Wie rechtfertigen Sie cata Fix t = t? Angenommen, Fix fdie anfängliche Algebra für fscheint 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.)
Li-yao Xia
Ich verstehe den Beweis der fixToMuSurjektivität nicht. "wenn wir ein forall a definieren wollen. (fa -> a) -> eine Funktion von Grund auf neu" Das wollen wir nicht. Lassen Sie k :: forall a. (f a -> a) -> auns stattdessen das k = \alg -> cata alg tfür einige zeigen t.
Li-yao Xia
[1/2] @ Li-yaoXia (1) Weiter cata Fixhaben wir cata Fix = Fix . fmap (cata Fix) . unfix. Wenn tkeine rekursiven Positionen vorhanden sind, fmap (cata Fix)wird nichts unternommen, und so weiter cata Fix t = Fix (unfix t) = t. Wenn es rekursive Positionen hat, fmap (cata Fix)wird es nur cata Fixauf sie angewendet , was ausreicht, um die Angelegenheit durch Induktion zu regeln.
Duplode
[2/2] @ Li-yaoXia (2) Zur Surjektivität: Das Argument ist, dass alles Mögliche kentweder durch direktes Anwenden der Algebra (für die ein f VoidWert benötigt wird) oder durch fmaprekursives 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.
Duplode
1
@ Li-yaoXia Ich habe die Sprache, die das Surjektivitätsargument beschreibt, optimiert und die cata Fix t = tAbleitung 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.
Duplode