wake-up-neo.com

Eine Monade ist nur ein Monoid in der Kategorie der Endofunktoren. Was ist das Problem?

Wer hat zuerst folgendes gesagt?

Eine Monade ist nur ein Monoid in der Kategorie der Endofunktoren. Was ist das Problem?

Und in einem weniger wichtigen Punkt, ist dies wahr und wenn ja, könnten Sie eine Erklärung abgeben (hoffentlich eine, die von jemandem verstanden werden kann, der nicht viel Erfahrung mit Haskell hat)?

698

Diese spezielle Formulierung stammt von James Iry aus seiner höchst unterhaltsamen Kurze, unvollständige und meist falsche Geschichte der Programmiersprachen, in der er sie fiktiv Philip zuschreibt Wadler.

Das Originalzitat stammt aus Saunders Mac Lane in Categories for the Working Mathematician , einem der Grundlagentexte der Kategorietheorie. Hier steht es im Zusammenhang , was wahrscheinlich der beste Ort ist, um genau zu lernen, was es bedeutet.

Aber ich werde einen Stich machen. Der ursprüngliche Satz lautet:

Alles in allem ist eine Monade in X nur ein Monoid in der Kategorie der Endofunktoren von X, wobei das Produkt × durch die Zusammensetzung der Endofunktoren und die vom Identitätsendofunktor festgelegte Einheit ersetzt wird.

X hier ist eine Kategorie. Endofunktoren sind Funktoren aus einer Kategorie für sich selbst (die in der Regel alle Functors sind, soweit es funktionale Programmierer betrifft, da sie sich meist nur mit einer Kategorie befassen: der Kategorie von Typen. Aber ich schweife ab). Sie können sich aber auch eine andere Kategorie vorstellen, nämlich die Kategorie "Endofunktoren auf X". Dies ist eine Kategorie, in der die Objekte Endofunktoren und die Morphismen natürliche Transformationen sind.

Und von diesen Endofunktoren könnten einige Monaden sein. Welche sind Monaden? Genau diejenigen, die in einem bestimmten Sinne monoidal sind. Anstatt die exakte Zuordnung von Monaden zu Monoiden zu formulieren (da Mac Lane das weitaus besser macht, als ich es mir erhoffen könnte), lege ich einfach die jeweiligen Definitionen nebeneinander und lasse Sie Folgendes vergleichen:

Ein Monoid ist ...

  • Eine Menge S
  • Eine Operation •: S × S → S
  • Ein Element von S, e: 1 → S

... diese Gesetze erfüllen:

  • (a • b) • c = a • (b • c) für alle a , b und c in S
  • e • a = a • e = a , für alle a in S

Eine Monade ist ...

  • Ein Endofunktor, T: X → X (in Haskell ein Typkonstruktor der Art * -> * mit einer Functor-Instanz)
  • Eine natürliche Transformation μ: T × T → T , wobei × bedeutet, dass die Funktorkomposition ( μ als join in Haskell bekannt ist.)
  • Eine natürliche Transformation η: I → T , wobei I ist der Identitätsendofunktor von X ( η ist bekannt als return in Haskell)

... diese Gesetze erfüllen:

  • μ ∘ Tμ = μ ∘ μT
  • μ ∘ Tη = μ ∘ ηT = 1 (die natürliche Identitätstransformation)

Mit ein wenig Schielen können Sie möglicherweise feststellen, dass beide Definitionen Instanzen desselben abstraktes Konzept sind.

764
Tom Crockett

Intuitiv denke ich, dass das ausgefallene mathematische Vokabular folgendes sagt:

Monoid

Ein Monoid ist eine Menge von Objekten und eine Methode, sie zu kombinieren. Bekannte Monoide sind:

  • zahlen, die Sie hinzufügen können
  • listen, die Sie verketten können
  • setzt du kannst gewerkschaft

Es gibt auch komplexere Beispiele.

Außerdem hat jedes Monoid ein Identität, also das "no-op" -Element, das beim Kombinieren keine Wirkung hat mit etwas anderem:

  • 0 + 7 == 7 + 0 == 7
  • [] ++ [1,2,3] == [1,2,3] ++ [] == [1,2,3]
  • {} union {Apple} == {Apple} union {} == {Apple}

Schließlich muss ein Monoid assoziativ sein. (Sie können beliebig viele Kombinationen reduzieren, solange Sie die Reihenfolge der Objekte von links nach rechts nicht ändern.) Das Hinzufügen ist in Ordnung ((5 + 3) +1 == 5+ (3+) 1)), aber Subtraktion ist nicht ((5-3) -1! = 5-1)).

Monade

Betrachten wir nun eine spezielle Art von Menge und eine spezielle Art, Objekte zu kombinieren.

Objekte

Angenommen, Ihre Menge enthält Objekte einer besonderen Art: --- (Funktionen. Und diese Funktionen haben eine interessante Signatur: Sie tragen keine Zahlen zu Zahlen oder Strings zu Strings. Stattdessen trägt jede Funktion in einem zweistufigen Prozess eine Nummer zu einer Liste von Nummern.

  1. Berechnen Sie 0 oder mehr Ergebnisse
  2. Kombinieren Sie diese Ergebnisse irgendwie zu einer einzigen Antwort.

Beispiele:

  • 1 -> [1] (nur die Eingabe umbrechen)
  • 1 -> [] (Eingabe verwerfen, Nichts in eine Liste aufnehmen)
  • 1 -> [2] (addiere 1 zu der Eingabe und wrappe das Ergebnis)
  • 3 -> [4, 6] (1 zur Eingabe hinzufügen und Eingabe mit 2 multiplizieren und die Mehrfachergebnisse umbrechen )

Objekte kombinieren

Auch unsere Art, Funktionen zu kombinieren, ist etwas Besonderes. Eine einfache Möglichkeit, eine Funktion zu kombinieren, ist Zusammensetzung : Nehmen wir unsere obigen Beispiele und setzen Sie jede Funktion mit sich selbst zusammen:

  • 1 -> [1] -> [[1]] (Eingabe zweimal umbrechen)
  • 1 -> [] -> [] (Eingabe verwerfen, Nichts zweimal in eine Liste aufnehmen)
  • 1 -> [2] -> [UH-OH! ] (Wir können einer Liste keine "1" hinzufügen! ")
  • 3 -> [4, 6] -> [UH-OH! ] (Wir können keine Liste hinzufügen!)

Ohne zu sehr auf die Typentheorie einzugehen, können Sie zwei Ganzzahlen kombinieren, um eine Ganzzahl zu erhalten, aber Sie können nicht immer zwei Funktionen zusammensetzen und eine Funktion desselben Typs erhalten. (Funktionen mit dem Typ a -> a werden komponiert, aber a-> [a] wird nicht.)

Definieren wir also eine andere Art, Funktionen zu kombinieren. Wenn wir zwei dieser Funktionen kombinieren, wollen wir die Ergebnisse nicht "doppelt verpacken".

Hier ist was wir tun. Wenn wir zwei Funktionen F und G kombinieren wollen, folgen wir diesem Prozess (genannt Bindung ):

  1. Berechnen Sie die "Ergebnisse" aus F, aber kombinieren Sie sie nicht.
  2. Berechnen Sie die Ergebnisse aus der Anwendung von G auf die einzelnen Ergebnisse von F, um eine Ergebnissammlung zu erhalten.
  3. Reduzieren Sie die 2-Ebenen-Sammlung und kombinieren Sie alle Ergebnisse.

Zurück zu unseren Beispielen, kombinieren wir eine Funktion mit sich selbst unter Verwendung dieser neuen Art der "Bindung" von Funktionen:

  • 1 -> [1] -> [1] (Eingabe zweimal umbrechen)
  • 1 -> [] -> [] (Eingabe verwerfen, Nichts zweimal in eine Liste aufnehmen)
  • 1 -> [2] -> [3] (addiere 1, addiere dann 1 erneut und wickle das Ergebnis um.)
  • 3 -> [4,6] -> [5,8,7,12] (Addiere 1 zur Eingabe und multipliziere auch die Eingabe mit 2, behalte beide Ergebnisse bei, dann mache alles noch einmal für beide Ergebnisse und wickle dann das Finale um ergibt eine Liste.)

Diese ausgefeiltere Art, Funktionen zu kombinieren , ist assoziativ (ausgehend davon, wie die Funktionszusammensetzung assoziativ ist, wenn Sie nicht das ausgefallene Wrapping-Zeug ausführen).

Alles zusammenbinden,

  • eine Monade ist eine Struktur, die eine Möglichkeit definiert, (die Ergebnisse von) Funktionen zu kombinieren.
  • analog dazu, wie ein Monoid eine Struktur ist, die einen Weg definiert, Objekte zu kombinieren,
  • wenn die Kombinationsmethode assoziativ ist,
  • und wo es ein spezielles 'No-op' gibt, das mit etwas kombiniert werden kann , um etwas zu ergeben unverändert.

Anmerkungen

Es gibt viele Möglichkeiten, Ergebnisse zu "verpacken". Sie können eine Liste oder einen Satz erstellen oder alle bis auf das erste Ergebnis verwerfen, während Sie feststellen, ob keine Ergebnisse vorliegen, einen Seitenwagen mit Status anhängen, eine Protokollnachricht drucken usw.

Ich habe ein bisschen locker mit den Definitionen gespielt, in der Hoffnung, die wesentliche Idee intuitiv zu vermitteln.

Ich habe die Dinge ein wenig vereinfacht, indem ich darauf bestanden habe, dass unsere Monade Funktionen vom Typ a -> [a] ausführt. Tatsächlich arbeiten Monaden mit Funktionen des Typs a -> m b , aber die Verallgemeinerung ist eine Art technisches Detail, das nicht die Haupteinsicht ist.

515
misterbee

Zunächst die Erweiterungen und Bibliotheken, die wir verwenden werden:

_{-# LANGUAGE RankNTypes, TypeOperators #-}

import Control.Monad (join)
_

Von diesen ist RankNTypes der einzige, der für das Folgende unbedingt erforderlich ist. Ich habe einmal eine Erklärung zu RankNTypes geschrieben, die einige Leute als nützlich empfunden haben , also werde ich darauf verweisen.

Zitat Tom Crocketts ausgezeichnete Antwort , wir haben:

Eine Monade ist ...

  • Ein Endofunktor, T: X -> X
  • Eine natürliche Transformation μ: T × T -> T, wobei × Funktorkomposition bedeutet
  • Eine natürliche Transformation, η: I -> T, wobei I die Identität ist endofunctor on X

... diese Gesetze erfüllen:

  • μ (μ (T × T) × T)) = μ (T × μ (T × T))
  • μ (η (T)) = T = μ (T (η))

Wie übersetzen wir das in Haskell-Code? Beginnen wir mit der Vorstellung einer natürlichen Transformation :

_-- | A natural transformations between two 'Functor' instances.  Law:
--
-- > fmap f . eta g == eta g . fmap f
--
-- Neat fact: the type system actually guarantees this law.
--
newtype f :-> g =
    Natural { eta :: forall x. f x -> g x }
_

Ein Typ der Form _f :-> g_ ist analog zu einem Funktionstyp, sieht ihn jedoch nicht als Funktion zwischen zwei Typen (von Art _*_), stellen Sie es sich als Morphismus zwischen zwei Funktoren (jeweils von Art _* -> *_). Beispiele:

_listToMaybe :: [] :-> Maybe
listToMaybe = Natural go
    where go [] = Nothing
          go (x:_) = Just x

maybeToList :: Maybe :-> []
maybeToList = Natural go
    where go Nothing = []
          go (Just x) = [x]

reverse' :: [] :-> []
reverse' = Natural reverse
_

Grundsätzlich sind natürliche Transformationen in Haskell Funktionen vom Typ _f x_ zu einem anderen Typ _g x_, sodass der Aufrufer auf die Variable vom Typ x nicht zugreifen kann. So kann beispielsweise _sort :: Ord a => [a] -> [a]_ nicht zu einer natürlichen Transformation gemacht werden, da es "wählerisch" ist, welche Typen wir für a instanziieren dürfen. Eine intuitive Art, wie ich das oft sehe, ist die folgende:

  • Ein Funktor ist eine Möglichkeit, den Inhalt ​​von etwas zu bearbeiten, ohne den Aufba zu berühren.
  • Eine natürliche Transformation ist ein Weg, an der Struktur von etwas zu arbeiten, ohne die Inhalte zu berühren oder zu betrachten.

Lassen Sie uns nun, da dies im Weg steht, die Klauseln der Definition in Angriff nehmen.

Die erste Klausel ist "ein Endofunktor, T: X -> X". Nun, jeder Functor in Haskell ist ein Endofunktor in der sogenannten "Hask-Kategorie", dessen Objekte Haskell-Typen (der Art _*_) und deren Morphismen Haskell-Funktionen sind. Das klingt nach einer komplizierten Aussage, ist aber eigentlich eine sehr triviale. Mit einem _Functor f :: * -> *_ können Sie einen Typ _f a :: *_ für einen beliebigen _a :: *_ und eine Funktion _fmap f :: f a -> f b_ aus einem beliebigen _f :: a -> b_ und erstellen dass diese die functor Gesetze befolgen.

Zweite Klausel: Der Identity-Funktor in Haskell (der mit der Plattform geliefert wird, sodass Sie ihn einfach importieren können) wird folgendermaßen definiert:

_newtype Identity a = Identity { runIdentity :: a }

instance Functor Identity where
    fmap f (Identity a) = Identity (f a)
_

So kann die natürliche Transformation η: I -> T aus Tom Crocketts Definition für jede Monad-Instanz t folgendermaßen geschrieben werden:

_return' :: Monad t => Identity :-> t
return' = Natural (return . runIdentity)
_

Dritte Klausel: Die Zusammensetzung von zwei Funktoren in Haskell kann folgendermaßen definiert werden (was auch mit der Plattform geliefert wird):

_newtype Compose f g a = Compose { getCompose :: f (g a) }

-- | The composition of two 'Functor's is also a 'Functor'.
instance (Functor f, Functor g) => Functor (Compose f g) where
    fmap f (Compose fga) = Compose (fmap (fmap f) fga)
_

Die natürliche Transformation μ: T × T -> T aus Tom Crocketts Definition kann also folgendermaßen geschrieben werden:

_join' :: Monad t => Compose t t :-> t
join' = Natural (join . getCompose)
_

Die Aussage, dass dies ein Monoid in der Kategorie der Endofunktoren ist, bedeutet dann, dass Compose (teilweise nur auf die ersten beiden Parameter angewendet) assoziativ ist und dass Identity sein Identitätselement ist. Das heißt, dass die folgenden Isomorphismen gelten:

  • Compose f (Compose g h) ~= Compose (Compose f g) h
  • _Compose f Identity ~= f_
  • _Compose Identity g ~= g_

Diese sind sehr einfach zu beweisen, da Compose und Identity beide als newtype definiert sind und die Haskell-Berichte die Semantik von newtype als Isomorphie zwischen dem zu definierenden Typ und dem Typ des Arguments für den Datenkonstruktor von newtype definieren. Beweisen wir also zum Beispiel _Compose f Identity ~= f_:

_Compose f Identity a
    ~= f (Identity a)                 -- newtype Compose f g a = Compose (f (g a))
    ~= f a                            -- newtype Identity a = Identity a
Q.E.D.
_
80
Luis Casillas

Hinweis: Nein, das ist nicht wahr. Irgendwann gab es einen Kommentar zu dieser Antwort von Dan Piponi selbst, in dem er sagte, dass die Ursache und Wirkung hier genau das Gegenteil sei. Er schrieb seinen Artikel als Antwort auf James Irys Witzbold. Aber es scheint entfernt worden zu sein, vielleicht durch eine zwanghafte Ordnung.

Unten ist meine ursprüngliche Antwort.


Es ist durchaus möglich, dass Iry Von Monoiden zu Monaden gelesen hatte, einen Beitrag, in dem Dan Piponi (Sigfpe) Monaden von Monoiden in Haskell herleitet, mit viel Diskussion über Kategorietheorie und ausdrücklicher Erwähnung der Kategorie der Endofunktoren am Hask ". Auf jeden Fall kann jeder, der sich fragt, was es bedeutet, dass eine Monade ein Monoid in der Kategorie der Endofunktoren ist, von dieser Ableitung profitieren.

6
hobbs

Ich bin zu diesem Beitrag gekommen, um die Schlussfolgerung des berüchtigten Zitats aus Mac Lanes Kategorietheorie für den arbeitenden Mathematiker besser zu verstehen.

Wenn man beschreibt, was etwas ist, ist es oft genauso nützlich, zu beschreiben, was es nicht ist.

Die Tatsache, dass Mac Lane die Beschreibung verwendet, um eine Monade zu beschreiben, könnte bedeuten, dass sie etwas beschreibt, das für Monaden einzigartig ist. Ertrage es mit mir Um ein umfassenderes Verständnis der Aussage zu entwickeln, muss meines Erachtens klargestellt werden, dass er nicht etwas beschreibt, das nur für Monaden gilt; Die Aussage beschreibt gleichermaßen unter anderem Applicative und Arrows. Aus dem gleichen Grund können wir zwei Monoide auf Int (Summe und Produkt) haben, wir können mehrere Monoide auf X in der Kategorie der Endofunktoren haben. Aber es gibt noch mehr Gemeinsamkeiten.

Sowohl Monad als auch Applicative erfüllen die Kriterien:

  • endo => jeder Pfeil oder Morphismus, der an derselben Stelle beginnt und endet
  • funktor => beliebiger Pfeil oder Morphismus zwischen zwei Kategorien

    (z. B. in Tag zu Tag Tree a -> List b, aber in Kategorie Tree -> List)

  • monoid => einzelnes Objekt; ein einzelner Typ, aber in diesem Zusammenhang nur in Bezug auf die äußere Schicht; Wir können also nicht Tree -> List haben, sondern nur List -> List.

In der Anweisung wird "Kategorie von ..." verwendet. Dies definiert den Umfang der Anweisung. Als Beispiel beschreibt die Functor-Kategorie den Umfang von f * -> g *, d. H. Any functor -> Any functor, z. B. Tree * -> List * oder Tree * -> Tree *.

Was in einer kategorialen Anweisung nicht angegeben ist, beschreibt, wo alles und jedes erlaubt ist .

In diesem Fall ist in den Funktoren * -> * aka a -> b nicht angegeben, was Anything -> Anything including Anything else bedeutet. Wenn meine Vorstellungskraft zu Int -> String springt, enthält sie auch Integer -> Maybe Int oder sogar Maybe Double -> Either String Int wobei a :: Maybe Double; b :: Either String Int.

Die Aussage fügt sich also wie folgt zusammen:

  • funktionsumfang :: f a -> g b (d. h. jeder parametrisierte Typ zu jedem parametrisierten Typ)
  • endo + functor :: f a -> f b (d. h. jeder parametrisierte Typ zu demselben parametrisierten Typ) ... anders gesagt,
  • ein Monoid in der Kategorie der Endofunktoren

Wo liegt also die Kraft dieses Konstrukts? Um die volle Dynamik zu erkennen, musste ich sehen, dass die typischen Zeichnungen eines Monoids (einzelnes Objekt mit einem Identitätspfeil, :: single object -> single object) nicht veranschaulichen, dass ich einen mit = parametrisierten Pfeil verwenden darf eine beliebige Anzahl von Monoid-Werten, vom Typ one , der in Monoid zulässig ist. Die Definition der Äquivalenz in endo, ~ identity arrow ignoriert des Funktors type value und sowohl der Typ als auch der Wert des Innersten. " Nutzlast "Schicht. Somit gibt die Äquivalenz true in jeder Situation zurück, in der die Funktortypen übereinstimmen (z. B. Nothing -> Just * -> Nothing ist äquivalent zu Just * -> Just * -> Just *, weil beide Maybe -> Maybe -> Maybe sind).

Sidebar: ~ outside ist konzeptionell, aber das Symbol ganz links in f a. Außerdem wird beschrieben, was "Haskell" zuerst einliest (großes Bild). Typ ist also "außerhalb" in Bezug auf einen Typwert. Die Beziehung zwischen Ebenen (eine Kette von Referenzen) in der Programmierung ist in der Kategorie nicht einfach zuzuordnen. Die Kategorie der Menge wird verwendet, um Typen (Int, Strings, Maybe Int usw.) zu beschreiben, einschließlich der Kategorie des Funktors (parametrisierte Typen). Die Referenzkette: Functor-Typ, Functor-Werte (Elemente des Functor-Satzes, z. B. Nothing, Just) und im Gegenzug alles andere, auf das jeder Functor-Wert verweist. In der Kategorie wird die Beziehung anders beschrieben, z. B. wird return :: a -> m a als natürliche Transformation von einem Functor zu einem anderen Functor betrachtet, die sich von den bisher genannten unterscheidet.

Alles in allem beschreibt die Aussage für jedes definierte Tensorprodukt und einen neutralen Wert ein erstaunlich leistungsfähiges Rechenkonstrukt, das aus seiner paradoxen Struktur hervorgeht:

  • auf der Außenseite erscheint es als ein einzelnes Objekt (z. B. :: List); statisch
  • aber innen erlaubt viel dynamik
    • beliebige Anzahl von Werten desselben Typs (z. B. Leer | ~ Nicht-Leer) als Futter für Funktionen beliebiger Art. Das Tensorprodukt reduziert eine beliebige Anzahl von Eingaben auf einen einzigen Wert ... für die externe Schicht (~ fold, die nichts über die Nutzlast aussagt)
    • unendlicher Bereich von beide Typ und Werte für die innerste Ebene

In Haskell ist es wichtig, die Anwendbarkeit der Aussage zu klären. Die Kraft und Vielseitigkeit dieses Konstrukts hat absolut nichts mit einer Monade zu tun per se . Mit anderen Worten, das Konstrukt beruht nicht auf dem, was eine Monade einzigartig macht.

Bei dem Versuch herauszufinden, ob Code mit einem gemeinsam genutzten Kontext erstellt werden soll, um voneinander abhängige Berechnungen zu unterstützen, im Gegensatz zu parallel ausgeführten Berechnungen, ist diese berüchtigte Aussage, so viel sie beschreibt, kein Kontrast zwischen der Auswahl von Applicative, Arrows and Monads, sondern beschreibt, wie viel sie gleich sind. Für die vorliegende Entscheidung ist die Aussage umstritten.

Dies wird oft missverstanden. In der Anweisung wird join :: m (m a) -> m a als Tensorprodukt für den monoiden Endofunktor beschrieben. Es wird jedoch nicht artikuliert, wie im Rahmen dieser Aussage auch (<*>) hätte gewählt werden können. Es ist wirklich ein Beispiel für sechs/ein halbes Dutzend. Die Logik zum Kombinieren von Werten ist genau gleich. Dieselbe Eingabe erzeugt von jeder die gleiche Ausgabe (im Gegensatz zu den Summen- und Produktmonoiden für Int, da sie beim Kombinieren von Ints unterschiedliche Ergebnisse erzeugen).

Um es noch einmal zusammenzufassen: Ein Monoid in der Kategorie der Endofunktoren beschreibt:

   ~t :: m * -> m * -> m *
   and a neutral value for m *

(<*>) und (>>=) bieten beide gleichzeitig Zugriff auf die beiden m Werte, um den einzelnen Rückgabewert zu berechnen. Die zur Berechnung des Rückgabewerts verwendete Logik ist genau dieselbe. Wenn es nicht die verschiedenen Formen der Funktionen gäbe, die sie parametrisieren (f :: a -> b versus k :: a -> m b) und die Position des Parameters mit dem gleichen Rückgabetyp der Berechnung (dh a -> b -> b versus b -> a -> b für jeden), ich vermute, wir hätten die monoidale Logik, das Tensorprodukt, für die Wiederverwendung in beiden Definitionen parametrisieren können. Versuchen Sie zur Verdeutlichung, ~t zu implementieren, und Sie erhalten (<*>) und (>>=), je nachdem, wie Sie es definieren forall a b.

Wenn mein letzter Punkt konzeptionell mindestens wahr ist, erklärt er den genauen und einzigen rechnerischen Unterschied zwischen Applicative und Monad: die Funktionen, die sie parametrisieren. Mit anderen Worten, der Unterschied ist external zur Implementierung dieser Typklassen.

Meiner eigenen Erfahrung nach lieferte Mac Lanes berüchtigtes Zitat ein großartiges "goto" -Mem, ein Wegweiser, auf den ich mich beziehen konnte, während ich mich durch Category bewegte, um die in Haskell verwendeten Redewendungen besser zu verstehen. Es gelingt, den Umfang einer in Haskell wunderbar zugänglichen leistungsfähigen Rechenkapazität zu erfassen.

Es ist jedoch ironisch, wie ich die Anwendbarkeit der Aussage außerhalb der Monade zum ersten Mal missverstanden habe und was ich hier hoffentlich vermittelt habe. Alles, was es beschreibt, stellt sich als das heraus, was zwischen Applicative und Monads (und unter anderem Arrows) ähnlich ist. Was es nicht sagt, ist genau die kleine, aber nützliche Unterscheidung zwischen ihnen.

- E

6
Edmund's Echo

Die Antworten hier leisten hervorragende Arbeit bei der Definition von Monoiden und Monaden, scheinen jedoch die Frage nicht zu beantworten:

Und in einem weniger wichtigen Punkt, ist dies wahr und wenn ja, könnten Sie eine Erklärung abgeben (hoffentlich eine, die von jemandem verstanden werden kann, der nicht viel Erfahrung mit Haskell hat)?

Der Kern der Sache, die hier fehlt, ist der unterschiedliche Begriff des "Monoids", die sogenannte Kategorisierung , genauer gesagt die des Monoids in einer monoiden Kategorie. Leider ist das Buch von Mac Lane selbst macht es sehr verwirrend :

Alles in allem ist eine Monade in X nur ein Monoid in der Kategorie der Endofunktoren von X, wobei das Produkt × durch die Zusammensetzung der Endofunktoren und die vom Identitätsendofunktor festgelegte Einheit ersetzt wird.

Hauptverwirrung

Warum ist das verwirrend? Weil es nicht definiert, was "Monoid in der Kategorie der Endofunktoren" von X ist. Stattdessen schlägt dieser Satz vor, ein Monoid in die Menge aller Endofunktoren zusammen mit der Funktorkomposition als binäre Operation und dem Identitätsfunktor als monoidale Einheit zu nehmen. Das funktioniert einwandfrei und verwandelt sich in eine beliebige Teilmenge von Endofunktoren, die den Identity-Funktor enthält und unter functor composition geschlossen ist.

Dies ist jedoch nicht die richtige Interpretation, die das Buch zu diesem Zeitpunkt nicht klar macht. Ein Monad f ist ein fester Endofunktor, keine Untermenge von unter Zusammensetzung geschlossenen Endofunktoren. Eine übliche Konstruktion besteht darin, f zu verwenden, um ein Monoid zu erzeugen , indem die Menge aller k -fachen Kompositionen f^k = f(f(...)) von f mit sich selbst genommen wird, einschließlich k=0, das der Identität entspricht f^0 = id. Und jetzt ist die Menge S aller dieser Potenzen für alle k>=0 in der Tat ein Monoid, "wobei das Produkt × durch die Zusammensetzung der Endofunktoren und die vom Identitätsendofunktor festgelegte Einheit ersetzt wird".

Und doch:

  • Dieses Monoid S kann für jede Funktion f oder sogar für jede Selbstabbildung von X definiert werden. Es ist das von f erzeugte Monoid.
  • Die monoide Struktur von S, die durch die Zusammensetzung des Funktors und den Identitätsfunktor vorgegeben wird, hat nichts damit zu tun, dass f eine Monade ist oder nicht.

Und um die Sache noch verwirrender zu machen, wird die Definition von "Monoid in monoidaler Kategorie" später in diesem Buch eingeführt, wie Sie aus dem Inhaltsverzeichnis ersehen können. Und doch ist das Verständnis dieses Begriffs für das Verständnis des Zusammenhangs mit Monaden von entscheidender Bedeutung.

(Strenge) monoide Kategorien

In Kapitel VII über Monoide (das später als Kapitel VI über Monaden erscheint) finden wir die Definition der sogenannten strengen monoiden Kategorie als Triple (B, *, e), wobei B eine Kategorie ist, *: B x B-> B a bifunctor (Funktor in Bezug auf jede Komponente mit einer anderen festen Komponente) und e ist ein Einheitsobjekt in B, das die Assoziativität und Einheitsgesetze erfüllt:

(a * b) * c = a * (b * c)
a * e = e * a = a

für alle Objekte a,b,c von B und die gleichen Identitäten für alle Morphismen a,b,c, wobei e durch id_e ersetzt wird, der Identitätsmorphismus von e. Es ist jetzt aufschlussreich zu beobachten, dass in unserem interessierenden Fall, in dem B die Kategorie der Endofunktoren von X mit natürlichen Transformationen als Morphismen, * die Funktorkomposition und e der Identitätsfunktor ist, alle diese Gesetze erfüllt sind, wie direkt verifiziert werden kann.

Was im Buch folgt, ist die Definition der "entspannten" monoiden Kategorie , in der die Gesetze nur einige feste natürliche Transformationen modulo enthalten, die sogenannte erfüllen. Kohärenzrelationen , die für unsere Fälle der Endofunktorkategorien jedoch nicht wichtig sind.

Monoide in monoiden Kategorien

Schließlich wird in Abschnitt 3 "Monoide" von Kapitel VII die eigentliche Definition gegeben:

Ein monoid c in einer monoidalen Kategorie (B, *, e) ist ein Objekt von B mit zwei Pfeilen (Morphismen)

mu: c * c -> c
nu: e -> c

3 Diagramme kommutativ machen. Denken Sie daran, dass es sich in unserem Fall um Morphismen in der Kategorie der Endofunktoren handelt, die natürliche Transformationen sind, die genau join und return für eine Monade entsprechen. Die Verbindung wird noch deutlicher, wenn wir die Komposition * expliziter gestalten und c * c durch c^2 ersetzen, wobei c unsere Monade ist.

Beachten Sie schließlich, dass die 3 Kommutativdiagramme (in der Definition eines Monoids in der Monoidkategorie) für allgemeine (nicht strenge) Monoidkategorien geschrieben sind, während in unserem Fall alle natürlichen Transformationen, die als Teil der Monoidkategorie auftreten, tatsächlich Identitäten sind. Dadurch stimmen die Diagramme genau mit denen in der Definition einer Monade überein, wodurch die Entsprechung vervollständigt wird.

Fazit

Zusammenfassend ist jede Monade per Definition ein Endofunktor, daher ein Objekt in der Kategorie der Endofunktoren, wobei die monadischen Operatoren join und return die Definition von eines Monoids in dieser bestimmten (strengen) monoiden Kategorie erfüllen . Umgekehrt ist jedes Monoid in der monoidalen Kategorie von Endofunktoren per Definition ein dreifacher (c, mu, nu), der aus einem Objekt und zwei Pfeilen besteht, z. natürliche Transformationen in unserem Fall, die die gleichen Gesetze wie eine Monade erfüllen.

Beachten Sie abschließend den Hauptunterschied zwischen den (klassischen) Monoiden und den allgemeineren Monoiden in monoiden Kategorien. Die beiden Pfeile mu und nu sind keine Binäroperation mehr und eine Einheit in einer Menge. Stattdessen haben Sie einen festen Endofunctor c. Die Funktorkomposition * und der Identitätsfunktor alleine bieten nicht die vollständige Struktur, die für die Monade benötigt wird, trotz dieser verwirrenden Bemerkung im Buch.

Ein anderer Ansatz wäre der Vergleich mit dem Standardmonoid C aller Selbstzuordnungen einer Menge A, wobei die Binäroperation die Zusammensetzung ist, die angezeigt wird, um das kartesische Standardprodukt C x C in C abzubilden. Übergabe an das kategorisierte Monoid, wir ersetzen das kartesische Produkt x durch die Funktorkomposition *, und die Binäroperation wird durch die natürliche Transformation mu von c * c in c ersetzt, dh durch eine Sammlung der Operatoren join

join: c(c(T))->c(T)

für jedes Objekt T (Programmierung eingeben). Und die Identitätselemente in klassischen Monoiden, die mit Abbildungen von Karten aus einer festen Einpunktmenge identifiziert werden können, werden durch die Auflistung der Operatoren return ersetzt

return: T->c(T) 

Aber jetzt gibt es keine kartesischen Produkte mehr, also keine Elementpaare und damit keine binären Operationen.

2
Dmitri Zaitsev