Monaden als Zusatz

Ich habe über Monaden in der Kategorietheorie gelesen. Eine Definition von Monaden verwendet ein Paar benachbarter Funktoren. Eine Monade wird durch eine Rundreise mit diesen Funktoren definiert. Anscheinend sind Zusätze in der Kategorietheorie sehr wichtig, aber ich habe keine Erklärung für Haskell-Monaden in Bezug auf benachbarte Funktoren gesehen. Hat jemand darüber nachgedacht?

Edit : Nur zum Spaß werde ich das richtig machen. Die ursprüngliche Antwort ist unten erhalten

Der aktuelle Zusatzcode für Kategorie-Extras befindet sich jetzt im Zusatzpaket: http://hackage.haskell.org/package/adjunctions

Ich werde die Staatsmonade nur explizit und einfach durcharbeiten. Dieser Code wird Data.Functor.Composeaus dem Transformers-Paket verwendet, ist aber ansonsten in sich geschlossen.

Eine Adjunktion zwischen f (D -> C) und g (C -> D), geschrieben f - | kann auf verschiedene Arten charakterisiert werden. Wir werden die Beschreibung von counit / unit (epsilon / eta) verwenden, die zwei natürliche Transformationen (Morphismen zwischen Funktoren) ergibt.

class (Functor f, Functor g) => Adjoint f g where
     counit :: f (g a) -> a
     unit   :: a -> g (f a)

Beachten Sie, dass das "a" im Rat wirklich der Identitätsfunktor in C ist und das "a" in der Einheit wirklich der Identitätsfunktion in D.

Wir können auch die Hom-Set-Adjunktionsdefinition aus der Counit / Unit-Definition wiederherstellen.

phiLeft :: Adjoint f g => (f a -> b) -> (a -> g b)
phiLeft f = fmap f . unit

phiRight :: Adjoint f g => (a -> g b) -> (f a -> b)
phiRight f = counit . fmap f

In jedem Fall können wir jetzt eine Monade aus unserer Einheit / Land-Adjunktion wie folgt definieren:

instance Adjoint f g => Monad (Compose g f) where
    return x = Compose $ unit x
    x >>= f  = Compose . fmap counit . getCompose $ fmap (getCompose . f) x

Jetzt können wir die klassische Adjunktion zwischen (a,) und (a ->) implementieren:

instance Adjoint ((,) a) ((->) a) where
    -- counit :: (a,a -> b) -> b
    counit (x, f) = f x
    -- unit :: b -> (a -> (a,b))
    unit x = \y -> (y, x)

Und jetzt ein Typensynonym

type State s = Compose ((->) s) ((,) s)

Und wenn wir dies in ghci laden, können wir bestätigen, dass State genau unsere klassische Staatsmonade ist. Beachten Sie, dass wir die entgegengesetzte Zusammensetzung verwenden und die Costate Comonad (auch bekannt als Store Comonad) erhalten können.

Es gibt eine Reihe anderer Zusätze, die wir auf diese Weise zu Monaden machen können (wie (Bool,) Pair), aber es sind seltsame Monaden. Leider können wir die Zusätze, die Reader und Writer direkt in Haskell veranlassen, nicht auf angenehme Weise vornehmen. Wir können Cont machen, aber wie Copumpkin beschreibt, erfordert dies eine Adjunktion aus einer entgegengesetzten Kategorie, sodass tatsächlich eine andere "Form" der Typklasse "Adjoint" verwendet wird, die einige Pfeile umkehrt. Dieses Formular ist auch in einem anderen Modul im Zusatzpaket implementiert.

Dieses Material wird auf andere Weise in Derek Elkins 'Artikel in The Monad Reader 13 - Berechnung von Monaden mit Kategorietheorie behandelt: http://www.haskell.org/wikiupload/8/85/TMR-Issue13.pdf

In Hinzes jüngstem Artikel "Kan Extensions for Program Optimization" (Kan-Erweiterungen für die Programmoptimierung) wird die Erstellung der Listenmonade anhand des Zusatzes zwischen Monund beschrieben Set: http://www.cs.ox.ac.uk/ralf.hinze/Kan.pdf

Alte Antwort:

Zwei Referenzen.

1) Kategorie-Extras liefern wie immer eine Darstellung der Zusätze und wie Monaden daraus entstehen. Wie üblich ist es gut zu denken, aber die Dokumentation ist ziemlich leicht: http://hackage.haskell.org/packages/archive/category-extras/0.53.5/doc/html/Control-Functor-Adjunction.html

2) -Cafe liefert auch eine vielversprechende, aber kurze Diskussion über die Rolle der Adjunktion. Einige davon können bei der Interpretation von Kategorie-Extras hilfreich sein: http://www.haskell.org/pipermail/haskell-cafe/2007-December/036328.html

Derek Elkins hat mir kürzlich beim Abendessen gezeigt, wie die Cont Monad entsteht, wenn man den (_ -> k)kontravarianten Funktor mit sich selbst komponiert , da er zufällig selbstadjunkt ist. So kommst du da (a -> k) -> kraus. Sein Rat führt jedoch zu einer Eliminierung der doppelten Negation, die nicht in Haskell geschrieben werden kann.

Einige Agda-Codes, die dies veranschaulichen und beweisen, finden Sie unter http://hpaste.org/68257 .

Dies ist ein alter Thread, aber ich fand die Frage interessant, also habe ich selbst einige Berechnungen durchgeführt. Hoffentlich ist Bartosz noch da und könnte das lesen ..

Tatsächlich liefert die Eilenberg-Moore-Konstruktion in diesem Fall ein sehr klares Bild. (Ich werde die CWM-Notation mit Haskell-ähnlicher Syntax verwenden.)

Sei Tdie Listenmonade < T,eta,mu >( eta = returnund mu = concat) und betrachte eine T-Algebra h:T a -> a.

(Beachten Sie, dass dies T a = [a]ein freies Monoid <[a],[],(++)>ist, dh Identität []und Multiplikation (++).)

Per Definition hmuss h.T h == h.mu aund erfüllen h.eta a== id.

Einige einfache Diagrammverfolgungen beweisen nun, dass htatsächlich eine Monoidstruktur auf einem (definiert durch x*y = h[x,y]) induziert wird und dass dies hein Monoidhomomorphismus für diese Struktur wird.

Umgekehrt wird jede < a,a0,* >in Haskell definierte Monoidstruktur natürlich als T-Algebra definiert.

Auf diese Weise ( h = foldr ( * ) a0eine Funktion , dass ‚ersetzt‘ (:)mit (*)und ordnet []an a0, die Identität).

In diesem Fall ist die Kategorie der T-Algebren nur die Kategorie der in Haskell, HaskMon, definierbaren Monoidstrukturen.

(Bitte überprüfen Sie, ob die Morphismen in T-Algebren tatsächlich monoide Homomorphismen sind.)

Es charakterisiert Listen auch als universelle Objekte in HaskMon, genau wie freie Produkte in Grp, Polynomringe in CRng usw.

Die der obigen Konstruktion entsprechende Einstellung ist < F,G,eta,epsilon >

wo

• F:Hask -> HaskMon, der einen Typ a zu dem 'freien Monoid erzeugt von a' nimmt, das heißt [a],
• G:HaskMon -> Hask, der vergessliche Funktor (vergiss die Multiplikation),
• eta:1 -> GF , die natürliche Transformation definiert durch \x::a -> [x],
• epsilon: FG -> 1 , die natürliche Transformation, die durch die obige Faltungsfunktion definiert ist (die 'kanonische Surjektion' von einem freien Monoid zu seinem Quotientenmonoid)

Als nächstes gibt es eine weitere 'Kleisli-Kategorie' und den entsprechenden Zusatz. Sie können überprüfen, ob es sich nur um die Kategorie der Haskell-Typen mit Morphismen handelt a -> T b, deren Zusammensetzung durch die sogenannte "Kleisli-Komposition" gegeben ist (>=>). Ein typischer Haskell-Programmierer wird diese Kategorie vertrauter finden.

Schließlich wird, wie in CWM dargestellt, die Kategorie der T-Algebren (bzw. Kleisli-Kategorie) das Endobjekt (bzw. die anfängliche) in der Kategorie der Adjunktionen, die die Listenmonade T in einem geeigneten Sinne definieren.

Ich schlage vor, ähnliche Berechnungen für den Binärbaum-Funktor durchzuführen T a = L a | B (T a) (T a), um Ihr Verständnis zu überprüfen.

Ich habe für jede Monade von Eilenberg-Moore eine Standardkonstruktion von Zusatzfunktoren gefunden, bin mir aber nicht sicher, ob sie dem Problem einen Einblick verleiht. Die zweite Kategorie in der Konstruktion ist eine Kategorie von T-Algebren. Die AT-Algebra fügt der ursprünglichen Kategorie ein "Produkt" hinzu.

Wie würde es für eine Listenmonade funktionieren? Der Funktor in der Listenmonade besteht beispielsweise aus einem Typkonstruktor Int->[Int]und einer Zuordnung von Funktionen (z. B. Standardanwendung der Zuordnung zu Listen). Eine Algebra fügt eine Zuordnung von Listen zu Elementen hinzu. Ein Beispiel wäre das Hinzufügen (oder Multiplizieren) aller Elemente einer Liste von ganzen Zahlen. Der Funktor Fnimmt einen beliebigen Typ, z. B. Int, und ordnet ihn der Algebra zu, die in den Listen von Int definiert ist, wobei das Produkt durch monadische Verknüpfung definiert wird (oder umgekehrt, Verknüpfung wird als Produkt definiert). Der vergessliche Funktor Gnimmt eine Algebra und vergisst das Produkt. Das Paar F, Gvon Adjunktion wird dann verwendet , um den monadisch in der üblichen Weise zu konstruieren.

Ich muss sagen, ich bin nicht klüger.

Wenn Sie interessiert sind, hier einige Gedanken eines Nicht-Experten zur Rolle von Monaden und Zusätzen in Programmiersprachen:

Erstens gibt es für eine bestimmte Monade Teine einzigartige Ergänzung zur Kategorie Kleisli von T. In Haskell beschränkt sich die Verwendung von Monaden hauptsächlich auf Operationen in dieser Kategorie (die im Wesentlichen eine Kategorie von freien Algebren ohne Quotienten ist). Tatsächlich kann man mit einer Haskell-Monade nur einige Kleisli-Morphismen des Typs a->T bunter Verwendung von do-Ausdrücken (>>=)usw. zusammensetzen, um einen neuen Morphismus zu erzeugen. In diesem Zusammenhang beschränkt sich die Rolle von Monaden nur auf die Ökonomie der Notation. Man nutzt die Assoziativität von Morphismen, um schreiben zu können (sagen wir), [0,1,2] anstatt (Cons 0 (Cons 1 (Cons 2 Nil))), dass Sie Sequenz als Sequenz schreiben können, nicht als Baum.

Selbst die Verwendung von E / A-Monaden ist nicht unbedingt erforderlich, da das derzeitige System vom Typ Haskell leistungsfähig genug ist, um die Datenkapselung (existenzielle Typen) zu realisieren.

Dies ist meine Antwort auf Ihre ursprüngliche Frage, aber ich bin gespannt, was Haskell-Experten dazu sagen.

Andererseits gibt es, wie wir bemerkt haben, auch eine 1-1-Entsprechung zwischen Monaden und Zusätzen zu (T-) Algebren. Adjoints sind nach MacLanes Worten "eine Möglichkeit, Äquivalenzen von Kategorien auszudrücken". In einer typischen Einstellung von Zusätzen, in <F,G>:X->Adenen Fes sich um eine Art 'freien Algebra-Generator' und G um einen 'vergesslichen Funktor' handelt, beschreibt die entsprechende Monade (unter Verwendung von T-Algebren), wie (und wann) die algebraische Struktur von aufgebaut Aist die Objekte von X.

Im Fall von Hask und der Listenmonade T ist die Struktur, die Teingeführt wird, die von Monoid, und dies kann uns helfen, Eigenschaften (einschließlich der Korrektheit) von Code durch algebraische Methoden zu ermitteln, die die Theorie der Monoide bereitstellt. Zum Beispiel kann die Funktion foldr (*) e::[a]->aleicht als assoziative Operation angesehen werden, solange <a,(*),e>es sich um ein Monoid handelt, eine Tatsache, die vom Compiler ausgenutzt werden könnte, um die Berechnung zu optimieren (z. B. durch Parallelität). Eine andere Anwendung besteht darin, "Rekursionsmuster" in der funktionalen Programmierung unter Verwendung kategorialer Methoden zu identifizieren und zu klassifizieren, in der Hoffnung, "das Goto der funktionalen Programmierung", Y (der willkürliche Rekursionskombinator), (teilweise) zu beseitigen.

Anscheinend ist diese Art von Anwendungen eine der Hauptmotivationen der Schöpfer der Kategorietheorie (MacLane, Eilenberg usw.), nämlich die natürliche Äquivalenz von Kategorien festzustellen und eine bekannte Methode in einer Kategorie auf eine andere zu übertragen (z homologische Methoden zu topologischen Räumen, algebraische Methoden zur Programmierung usw.). Adjunkte und Monaden sind hier unverzichtbare Werkzeuge, um diese Verbindung von Kategorien auszunutzen. (Übrigens ist der Begriff der Monaden (und seiner dualen Comonaden) so allgemein, dass man sogar so weit gehen kann, "Kohomologien" von Haskell-Typen zu definieren. Aber ich habe noch nicht darüber nachgedacht.)

Was nicht deterministische Funktionen betrifft, die Sie erwähnt haben, habe ich viel weniger zu sagen ... Aber beachten Sie, dass; Wenn ein Zusatz <F,G>:Hask->Afür eine Kategorie Adie Listenmonade definiert T, muss es einen eindeutigen "Vergleichsfunktor" geben K:A->MonHask(die in Haskell definierbare Kategorie von Monoiden), siehe CWM. Dies bedeutet im Endeffekt, dass Ihre interessierende Kategorie eine Kategorie von Monoiden in einer eingeschränkten Form sein muss (z. B. fehlen möglicherweise einige Quotienten, aber keine freien Algebren), um die Listenmonade zu definieren.

Zum Schluss noch einige Bemerkungen:

Der in meinem letzten Beitrag erwähnte Binärbaum-Funktor lässt sich leicht auf einen beliebigen Datentyp verallgemeinern T a1 .. an = T1 T11 .. T1m | .... Jeder Datentyp in Haskell definiert natürlich eine Monade (zusammen mit der entsprechenden Kategorie von Algebren und der Kleisli-Kategorie), die nur das Ergebnis eines Gesamtdatenkonstruktors in Haskell ist. Dies ist ein weiterer Grund, warum ich denke, dass Haskells Monad-Klasse nicht viel mehr als ein Syntaxzucker ist (was in der Praxis natürlich ziemlich wichtig ist).