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

723

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 geben (hoffentlich eine, die von jemandem verstanden werden kann, der nicht viel Erfahrung mit Haskell hat)?

Roman A. Taycher
quelle
14
Siehe "Kategorien für den arbeitenden Mathematiker"
Don Stewart
19
Sie müssen dies nicht verstehen, um Monaden in Haskell zu verwenden. Aus praktischer Sicht sind sie nur eine clevere Möglichkeit, den "Staat" durch unterirdische Rohrleitungen zu umgehen.
Starblue
1
Ich möchte diesen ausgezeichneten Blog-Beitrag auch hier hinzufügen: stephendiehl.com/posts/monads.html Er beantwortet die Frage nicht direkt, aber meiner Meinung nach leistet Stephen hervorragende Arbeit, um Kategorien und Monaden in Haskell miteinander zu verbinden. Wenn Sie die obigen Antworten gelesen haben, sollte dies dazu beitragen, die beiden Betrachtungsweisen zu vereinheitlichen.
Ben Ford
3
Genauer gesagt "Für jede Kategorie C hat die Kategorie [C, C] ihrer Endofunktoren eine durch die Zusammensetzung induzierte monoidale Struktur. Ein monoides Objekt in [C, C] ist eine Monade auf C." - von en.wikipedia.org/wiki/Monoid_%28category_theory%29. Siehe en.wikipedia.org/wiki/Monad_%28category_theory%29 für die Definition der Monade in der Kategorietheorie.
1
@Dmitry Ein Funktor ist eine Funktion zwischen Kategorien, mit einigen Einschränkungen, um sich gut zu benehmen. Ein Endofunktor in einer Kategorie C ist nur ein Funktor von C zu sich selbst. Data.Functor ist eine Typklasse für Endofunktoren in der Kategorie Hask . Da eine Kategorie aus Objekten und Morphismen besteht, muss ein Funktor beide abbilden. Für eine Instanz f von Data.Functor ist die Karte auf Objekten (Haskell-Typen) f selbst und die Karte auf Morphismen (Haskell-Funktionen) ist fmap.
Matthijs

Antworten:

796

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

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

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

Insgesamt 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 Einheit ersetzt wird, die vom Identitätsendofunktor festgelegt werden.

X hier ist eine Kategorie. Endofunktoren sind Funktoren von einer Kategorie zu sich selbst (was für funktionale Programmierer normalerweise alles ist Functor , da es sich meistens nur um eine Kategorie handelt; die Kategorie der 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 genaue Zuordnung von Monaden zu Monoiden zu formulieren (da Mac Lane dies weitaus besser macht, als ich es mir erhoffen könnte), werde ich einfach ihre jeweiligen Definitionen nebeneinander stellen und Sie vergleichen lassen:

Ein Monoid ist ...

  • Ein Satz, 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 * -> *mit einer FunctorInstanz)
  • Eine natürliche Transformation, μ: T × T → T , wobei × die Zusammensetzung des Funktors bedeutet ( μ ist bekannt als joinin Haskell).
  • Eine natürliche Transformation, η: I → T , wobei I der Identitätsendofunktor auf X ist ( η ist bekannt als returnin Haskell)

... diese Gesetze erfüllen:

  • μ ∘ Tμ = μ ∘ μT
  • μ ∘ Tη = μ ∘ ηT = 1 (die natürliche Transformation der Identität)

Mit ein wenig Schielen können Sie möglicherweise erkennen, dass beide Definitionen Instanzen desselben abstrakten Konzepts sind .

Tom Crockett
quelle
21
Vielen Dank für die Erklärung und den Artikel über die kurze, unvollständige und meist falsche Geschichte der Programmiersprachen. Ich dachte, es könnte von dort sein. Wirklich eines der größten Programmierhumorstücke.
Roman A. Taycher
6
@ Jonathan: In der klassischen Formulierung eines Monoids bedeutet × das kartesische Produkt von Mengen. : Sie können mehr über das hier lesen en.wikipedia.org/wiki/Cartesian_product , aber die Grundidee ist , dass ein Element von S × T ist ein Paar (s, t) , wobei s ∈ S und t ∈ T . Die Signatur des monoidalen Produkts •: S × S -> S bedeutet in diesem Zusammenhang einfach eine Funktion, die 2 Elemente von S als Eingabe verwendet und ein weiteres Element von S als Ausgabe erzeugt.
Tom Crockett
12
@TahirHassan - In der Allgemeinheit der Kategorietheorie beschäftigen wir uns mit undurchsichtigen "Objekten" anstelle von Mengen, und daher gibt es keinen a priori Begriff von "Elementen". Wenn Sie jedoch an die Kategorie Menge denken, in der die Objekte Mengen und die Pfeile Funktionen sind, stimmen die Elemente einer Menge S eins zu eins mit den Funktionen einer Menge von einem Element auf S überein. Das heißt, für jede Element e von S gibt es genau eine Funktion f: 1 -> S , wobei 1 eine beliebige Ein-Element-Menge ist ... (Fortsetzung)
Tom Crockett
12
@ TahirHassan 1-Element-Mengen sind selbst Spezialisierungen des allgemeineren kategorietheoretischen Begriffs "Terminalobjekte": Ein Terminalobjekt ist ein Objekt einer Kategorie, für das es genau einen Pfeil von einem anderen Objekt gibt (Sie können dies überprüfen) Dies gilt für 1-Element-Sets in Set . In der Kategorietheorie werden Terminalobjekte einfach als 1 bezeichnet ; Sie sind bis zum Isomorphismus einzigartig, daher macht es keinen Sinn, sie zu unterscheiden. Jetzt haben wir eine rein kategorietheoretische Beschreibung der "Elemente von S " für jedes S : Sie sind nur die Pfeile von 1 bis S !
Tom Crockett
7
@TahirHassan - Um dies in Haskell-Begriffen auszudrücken, denken Sie an die Tatsache, dass Sie, wenn Ses sich um einen Typ handelt, beim Schreiben einer Funktion f :: () -> Snur einen bestimmten Typbegriff auswählen können S(ein "Element" davon, wenn Sie so wollen) und zurückkehren it ... Sie haben mit dem Argument keine wirklichen Informationen erhalten, daher gibt es keine Möglichkeit, das Verhalten der Funktion zu variieren. Es fmuss also eine konstante Funktion sein, die jedes Mal dasselbe zurückgibt. ()("Einheit") ist das Endobjekt der Kategorie Hask , und es ist kein Zufall, dass es genau 1 (nicht divergierenden) Wert gibt, der es bewohnt.
Tom Crockett
532

Intuitiv denke ich, dass das ausgefallene Mathematikvokabular 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
  • Sätze können Sie Union

Es gibt auch komplexere Beispiele.

Außerdem hat jedes Monoid eine Identität , dh das "No-Op" -Element, das keine Wirkung hat, wenn Sie es mit etwas anderem kombinieren:

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

Schließlich muss ein Monoid sein assoziativ sein . (Sie können eine lange Folge von Kombinationen beliebig reduzieren, solange Sie die Reihenfolge der Objekte von links nach rechts nicht ändern.) Die Addition ist OK ((5 + 3) +1 == 5+ (3+) 1)), aber Subtraktion ist nicht ((5-3) -1! = 5- (3-1)).

Monade

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

Objekte

Angenommen, Ihr Set enthält Objekte einer besonderen Art: Funktionen . Und diese Funktionen haben eine interessante Signatur: Sie tragen keine Zahlen zu Zahlen oder Zeichenfolgen zu Zeichenfolgen. Stattdessen überträgt jede Funktion in einem zweistufigen Prozess eine Nummer in eine Liste von Nummern.

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

Beispiele:

  • 1 -> [1] (einfach die Eingabe umbrechen)
  • 1 -> [] (Eingabe verwerfen, Nichts in eine Liste einschließen)
  • 1 -> [2] (1 zur Eingabe hinzufügen und das Ergebnis umbrechen)
  • 3 -> [4, 6] (addiere 1 zur Eingabe und multipliziere die Eingabe mit 2 und verpacke die mehreren Ergebnisse )

Objekte kombinieren

Auch unsere Art, Funktionen zu kombinieren, ist etwas Besonderes. Eine einfache Möglichkeit, Funktionen zu kombinieren, ist die Komposition : Nehmen wir unsere obigen Beispiele und komponieren jede Funktion mit sich selbst:

  • 1 -> [1] -> [[1]] (Eingabe zweimal umbrechen)
  • 1 -> [] -> [] (Eingabe verwerfen, Nichts in eine Liste einschließen, zweimal)
  • 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 sich zu sehr mit der Typentheorie zu befassen, besteht der Punkt darin, dass Sie zwei Ganzzahlen kombinieren können, um eine Ganzzahl zu erhalten, aber Sie können nicht immer zwei Funktionen zusammensetzen und eine Funktion desselben Typs erhalten. (Funktionen mit Typ a -> a werden komponiert, a-> [a] jedoch nicht.)

Definieren wir also eine andere Art, Funktionen zu kombinieren. Wenn wir zwei dieser Funktionen kombinieren, möchten wir die Ergebnisse nicht doppelt umbrechen.

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

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

Zurück zu unseren Beispielen: Kombinieren (binden) wir eine Funktion mit sich selbst, indem wir diese neue Art der "Bindung" von Funktionen verwenden:

  • 1 -> [1] -> [1] (Eingabe zweimal umbrechen)
  • 1 -> [] -> [] (Eingabe verwerfen, Nichts in eine Liste einschließen, zweimal)
  • 1 -> [2] -> [3] (addiere 1, füge dann 1 hinzu und verpacke das Ergebnis.)
  • 3 -> [4,6] -> [5,8,7,12] (addiere 1 zur Eingabe und multipliziere auch die Eingabe mit 2, behalte beide Ergebnisse bei, mache dann alles noch einmal zu beiden Ergebnissen und beende dann das Finale führt zu einer Liste.)

Diese ausgefeiltere Art, Funktionen zu kombinieren, ist assoziativ (nach der Assoziationszusammensetzung, wenn Sie nicht das ausgefallene Wrapping-Zeug machen).

Alles zusammenbinden,

  • Eine Monade ist eine Struktur, die einen Weg definiert, um (die Ergebnisse von) Funktionen zu kombinieren.
  • analog dazu, wie ein Monoid eine Struktur ist, die einen Weg zum Kombinieren von Objekten definiert,
  • wo die Kombinationsmethode assoziativ ist,
  • und wo es ein spezielles 'No-op' gibt, das mit etwas kombiniert werden kann , um etwas Unverändertes zu ergeben.

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. 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 an Funktionen vom Typ a -> mb , aber die Verallgemeinerung ist eine Art technisches Detail, das nicht die Haupterkenntnis ist.

Misterbee
quelle
22
Dies ist eine schöne Erklärung dafür, wie jede Monade eine Kategorie darstellt (die Kategorie Kleisli ist das, was Sie demonstrieren - es gibt auch die Kategorie Eilenberg-Moore). Aufgrund der Tatsache, dass Sie keine zwei Kleisli-Pfeile zusammensetzen können a -> [b]und c -> [d](Sie können dies nur tun, wenn b= c), beschreibt dies kein Monoid. Es ist eigentlich die von Ihnen beschriebene Abflachungsoperation und nicht die Funktionszusammensetzung, die der "Monoidoperator" ist.
Tom Crockett
6
Zugegeben, wenn Sie eine Monade auf nur einen Typ beschränken, dh wenn Sie nur Kleisli-Pfeile der Form zulassen a -> [a], wäre dies ein Monoid (da Sie die Kleisli-Kategorie auf ein einzelnes Objekt und jede Kategorie von nur einem Objekt reduzieren würden ist per Definition ein Monoid!), aber es würde nicht die volle Allgemeinheit der Monade erfassen.
Tom Crockett
5
Bei der letzten Anmerkung ist es hilfreich, sich daran zu erinnern, dass a -> [a] nur a -> [] a ist. ([] ist auch nur ein Typkonstruktor.) Und so kann es nicht nur als -> mb angesehen werden, sondern [] ist in der Tat eine Instanz der Monad-Klasse.
Evi1M4chine
8
Dies ist die beste und am besten geeignete Erklärung für Monaden und ihren mathematischen Hintergrund für Monoide, die mir in buchstäblich Wochen begegnet sind. Dies sollte zweifellos in jedem Haskell-Buch abgedruckt werden, wenn es um Monaden geht. UPVOTE! Vielleicht erhalten Sie weiter die Information, dass Monaden als parametrisierte Typklasseninstanzen realisiert werden, die alles, was in Haschell enthalten ist, in den Post einwickeln. (Zumindest habe ich sie inzwischen so verstanden. Korrigieren Sie mich, wenn ich falsch liege . Siehe haskell.org/haskellwiki/What_a_Monad_is_not )
sjas
1
Das ist fantastisch - es ist die einzige Erklärung, die ich gut genug verstanden habe, um sie jemand anderem erklären zu können ... Aber ich verstehe immer noch nicht, warum dies eine wertvolle Art ist, an irgendetwas zu denken. :(
Adam Barnes
84

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

{-# LANGUAGE RankNTypes, TypeOperators #-}

import Control.Monad (join)

Von diesen RankNTypesist die einzige, die für das Folgende absolut notwendig ist. Ich habe einmal eine Erklärung dafür geschrieben, RankNTypesdass einige Leute es nützlich gefunden haben , also werde ich darauf verweisen.

Wir zitieren Tom Crocketts ausgezeichnete Antwort und 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 der Identitätsendofunktor auf X ist

... 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 :-> gist analog zu einem Funktionstyp, aber anstatt ihn als eine Funktion zwischen zwei Typen (von Art *) zu betrachten, betrachten Sie ihn als einen Morphismus zwischen zwei Funktoren (jeder 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 in Haskell natürliche Transformationen Funktionen von einem Typ f xzu einem anderen Typ, g xso dass die xTypvariable für den Aufrufer "unzugänglich" ist. So kann zum Beispiel sort :: Ord a => [a] -> [a]nicht zu einer natürlichen Transformation gemacht werden, weil es "wählerisch" ist, für welche Typen wir instanziieren können a. Eine intuitive Art, wie ich oft daran denke, ist die folgende:

  • Ein Funktor ist eine Möglichkeit, den Inhalt von etwas zu bearbeiten, ohne die Struktur zu berühren .
  • Eine natürliche Transformation ist eine Möglichkeit, die Struktur von etwas zu bearbeiten, ohne den Inhalt zu berühren oder zu betrachten .

Lassen Sie uns nun, da dies nicht im Weg ist, die Klauseln der Definition angehen.

Die erste Klausel ist "ein Endofunktor, T: X -> X. " Nun, jeder Functorin Haskell ist ein Endofunktor in der sogenannten "Hask-Kategorie", deren Objekte Haskell-Typen (von Art *) und deren Morphismen Haskell-Funktionen sind. Das klingt nach einer komplizierten Aussage, ist aber eigentlich eine sehr triviale. Alles was es bedeutet ist, dass a Functor f :: * -> *Ihnen die Möglichkeit gibt, einen Typ f a :: *für jeden a :: *und eine Funktion fmap f :: f a -> f baus jedem zu konstruieren f :: a -> b, und dass diese den Funktorgesetzen gehorchen.

Zweite Klausel: Der IdentityFunktor 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)

Die natürliche Transformation η: I -> T aus Tom Crocketts Definition kann also für jeden MonadFall so geschrieben werden t:

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 dies Identitysein 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 leicht zu beweisen , da Composeund Identitybeide definiert als newtypeund die Haskell Reports definieren die Semantik newtypeals ein Isomorphismus zwischen dem Typ definiert ist und den Typ des Arguments an die newtype‚s Daten Konstruktor. Lassen Sie uns zum Beispiel beweisen 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.
Luis Casillas
quelle
Im NaturalNewtype kann ich nicht herausfinden, was die (Functor f, Functor g)Einschränkung bewirkt . Könntest du erklären?
Feuer
@dfeuer Es macht eigentlich nichts Wesentliches.
Luis Casillas
1
@ LuisCasillas Ich habe diese FunctorEinschränkungen entfernt , da sie nicht notwendig erscheinen. Wenn Sie nicht einverstanden sind, können Sie sie wieder hinzufügen.
Lambda-Fee
Können Sie näher erläutern, was es formal bedeutet, wenn das Produkt von Funktoren als Komposition betrachtet wird? Was sind insbesondere die Projektionsmorphismen für die Funktorkomposition? Ich vermute, dass das Produkt nur für einen Funktor F gegen sich selbst, F x F und nur dann joindefiniert ist, wenn es definiert ist. Und dasjoin ist der Projektionsmorphismus. Aber ich bin mir nicht sicher.
Tksfz
6

Hinweis: Nein, das stimmt nicht. Irgendwann gab es einen Kommentar zu dieser Antwort von Dan Piponi selbst, der sagte, dass Ursache und Wirkung hier genau das Gegenteil waren, dass er seinen Artikel als Antwort auf James Irys Scherz schrieb. Aber es scheint entfernt worden zu sein, vielleicht durch einen zwanghaften Aufräumer.

Unten ist meine ursprüngliche Antwort.


Es ist gut möglich, dass Iry gelesen hat From Monoids to Monads , einen Beitrag, in dem Dan Piponi (sigfpe) Monaden von Monoids in Haskell ableitet, mit viel Diskussion über Kategorietheorie und expliziter Erwähnung von "der Kategorie der Endofunktoren auf Hask ". In jedem Fall könnte jeder, der sich fragt, was es für eine Monade bedeutet, ein Monoid in der Kategorie der Endofunktoren zu sein, davon profitieren, diese Ableitung zu lesen.

Hobbs
quelle
1
"Vielleicht durch einen zwanghaften Aufräumer" - oder, wie wir auf dieser Seite gerne darauf verweisen, einen Moderator :-).
halfer
6

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

Bei der Beschreibung, was etwas ist, ist es oft gleichermaßen 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 Einzigartiges für Monaden beschreibt. Trage es mit mir. Um ein breiteres 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 unter anderem Applicative und Arrows gleichermaßen. 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 die Ähnlichkeiten haben noch mehr zu bieten.

Sowohl Monad als auch Applicative erfüllen die Kriterien:

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

    (zB Tag für Tag Tree a -> List b, aber in Kategorie Tree -> List)

  • Monoid => einzelnes Objekt; dh ein einzelner Typ, jedoch in diesem Zusammenhang nur in Bezug auf die äußere Schicht; Also können wir nicht Tree -> Listnur haben List -> List.

Die Anweisung verwendet "Kategorie von ...". Dies definiert den Umfang der Anweisung. Als Beispiel beschreibt die Funktorkategorie den Umfang f * -> g *, das heißt Any functor -> Any functor, zum Beispiel Tree * -> List *oder Tree * -> Tree *.

Was eine kategoriale Aussage nicht spezifiziert, beschreibt, wo alles und jedes erlaubt ist .

In diesem Fall ist innerhalb der Funktoren * -> *aka a -> bnicht angegeben, was bedeutet Anything -> Anything including Anything else. Wenn meine Fantasie zu Int -> String springt, schließt es auch ein Integer -> Maybe Intoder sogar Maybe Double -> Either String Intwo a :: Maybe Double; b :: Either String Int.

Die Aussage lautet also wie folgt:

  • Funktionsbereich :: f a -> g b(dh ein beliebiger parametrisierter Typ zu einem beliebigen parametrisierten Typ)
  • endo + functor :: f a -> f b(dh jeder parametrisierte Typ zum gleichen parametrisierten Typ) ... anders gesagt,
  • ein Monoid in der Kategorie Endofunctor

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 Pfeil verwenden darf, der mit einer beliebigen Anzahl von Monoidwerten parametrisiert ist. von dem einem Typ Objekt erlaubte in Monoid. Die endo, ~ Identität Pfeil Definition der Gleichwertigkeit ignoriert die von Funktors Typwert und sowohl die Art und den Wert der innersten „Nutzlast“ Schicht. Somit kehrt die Äquivalenz truein jeder Situation zurück, in der die Funktionstypen übereinstimmen (z. B. Nothing -> Just * -> Nothingist äquivalent zu, Just * -> Just * -> Just *weil sie beide sind Maybe -> Maybe -> Maybe).

Seitenleiste: ~ außerhalb ist konzeptionell, aber das Symbol ganz links in f a. Es beschreibt auch, was "Haskell" zuerst einliest (großes Bild); Typ ist also "außerhalb" in Bezug auf einen Typwert. Die Beziehung zwischen Ebenen (einer Referenzkette) bei der Programmierung ist in der Kategorie nicht einfach zu beschreiben. Die Kategorie des Satzes wird verwendet, um Typen (Int, Strings, Vielleicht Int usw.) zu beschreiben, die die Kategorie des Funktors (parametrisierte Typen) enthalten. Die Referenzkette: Funktortyp, Funktorwerte (Elemente des Funktorsatzes, z. B. Nothing, Just) und alles andere, auf das jeder Funktorwert verweist. In der Kategorie wird die Beziehung anders beschrieben, z. B. return :: a -> m awird sie als natürliche Transformation von einem Funktor zu einem anderen Funktor angesehen, anders als alles, was bisher erwähnt wurde.

Zurück zum Hauptthema: 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:

  • außen erscheint es als einzelnes Objekt (zB :: List); statisch
  • aber innen erlaubt viel Dynamik
    • Beliebig viele Werte 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 (~ folddas sagt nichts über die Nutzlast aus)
    • unendlicher Bereich sowohl des Typs als auch der Werte für die innerste Schicht

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

Bei dem Versuch herauszufinden, ob Code mit einem gemeinsamen Kontext erstellt werden soll, um voneinander abhängige Berechnungen zu unterstützen, im Vergleich zu Berechnungen, die parallel ausgeführt werden können, ist diese berüchtigte Aussage, so viel sie beschreibt, kein Kontrast zwischen der Wahl von Anwendbar, Pfeile und Monaden, sondern beschreibt, wie sehr sie gleich sind. Für die vorliegende Entscheidung ist die Aussage umstritten.

Dies wird oft missverstanden. In der Erklärung wird join :: m (m a) -> m adas Tensorprodukt für den monoidalen Endofunktor beschrieben. Es wird jedoch nicht dargelegt, wie im Rahmen dieser Aussage (<*>)auch auch gewählt werden könnte. Es ist wirklich ein Beispiel für sechs / ein halbes Dutzend. Die Logik zum Kombinieren von Werten ist genau gleich. Dieselbe Eingabe generiert jeweils 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 (>>=)beide bieten gleichzeitigen Zugriff auf die beiden mWerte, um den einzelnen Rückgabewert zu berechnen. Die zur Berechnung des Rückgabewerts verwendete Logik ist genau dieselbe. Ohne die unterschiedlichen Formen der Funktionen, die sie parametrisieren ( f :: a -> bversus k :: a -> m b), und die Position des Parameters mit dem gleichen Rückgabetyp der Berechnung (dh a -> b -> bversus b -> a -> bfür jeden), hätten wir vermutlich die monoidale Logik parametrisieren können, die Tensorprodukt zur Wiederverwendung in beiden Definitionen. Versuchen ~tSie als Übung, den Punkt zu verdeutlichen, ihn umzusetzen , und Sie erhalten (<*>)und (>>=)hängen davon ab, wie Sie ihn definieren forall a b.

Wenn mein letzter Punkt konzeptionell mindestens wahr ist, erklärt er den genauen und einzigen rechnerischen Unterschied zwischen Applikativ und Monade: die Funktionen, die sie parametrisieren. Mit anderen Worten, der Unterschied liegt außerhalb der Implementierung dieser Typklassen.

Nach meiner eigenen Erfahrung lieferte Mac Lanes berüchtigtes Zitat ein großartiges "goto" -Mem, ein Wegweiser, auf den ich mich beim Navigieren durch die Kategorie beziehen konnte, um die in Haskell verwendeten Redewendungen besser zu verstehen. Es gelingt ihm, den Umfang einer leistungsstarken Rechenkapazität zu erfassen, die in Haskell wunderbar zugänglich gemacht wird.

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

- E.

Edmunds Echo
quelle
5

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

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

Der Kern der Sache, die hier fehlt, ist der andere Begriff des "Monoids", genauer gesagt die sogenannte Kategorisierung - die des Monoids in einer monoidalen Kategorie. Leider macht Mac Lanes Buch selbst es sehr verwirrend :

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

Hauptverwirrung

Warum ist das verwirrend? Weil es nicht definiert, was "Monoid in der Kategorie der Endofunktoren" von ist X. Stattdessen schlägt dieser Satz vor, ein Monoid innerhalb der 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 ein Monoid jeder Untergruppe von Endofunktoren, die den Identitätsfunktor enthält und unter Funktorkomposition geschlossen ist.

Dies ist jedoch nicht die richtige Interpretation, die das Buch zu diesem Zeitpunkt nicht klar macht. Eine Monade fist ein fester Endofunktor, keine Teilmenge von Endofunktoren, die unter Zusammensetzung geschlossen sind. Eine übliche Konstruktion besteht darin f, ein Monoid zu erzeugen, indem der Satz aller kKompositionen f^k = f(f(...))von fsich genommen wird, einschließlich k=0derjenigen, die der Identität entsprechen f^0 = id. Und jetzt ist die Menge Sall dieser Kräfte für alle k>=0in 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 Skann für jeden Funktor foder sogar wörtlich für jede Selbstkarte von definiert werden X. Es ist das Monoid, das von erzeugt wird f.
  • Die monoidale Struktur Sder Funktorkomposition und des Identitätsfunktors hat nichts damit zu tun f, eine Monade zu sein oder nicht.

Und um die Sache noch verwirrender zu machen, wird die Definition von "Monoid in monoidaler Kategorie" später in diesem Buch veröffentlicht, wie Sie dem Inhaltsverzeichnis entnehmen können . Das Verständnis dieser Vorstellung ist jedoch absolut entscheidend für das Verständnis der Verbindung mit Monaden.

(Strenge) monoidale Kategorien

Wenn wir zu Kapitel VII über Monoide gehen (das später als Kapitel VI über Monaden erscheint), finden wir die Definition der sogenannten strengen monoidalen Kategorie als dreifach (B, *, e), wobei Beine Kategorie, *: B x B-> Bein Bifunktor (Funktor in Bezug auf jede Komponente mit einer anderen festen Komponente) ist ) und eist ein Einheitsobjekt in B, das die Assoziativitäts- und Einheitsgesetze erfüllt:

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

für alle Objekte a,b,caus B, und die gleichen Identitäten für alle Morphismen a,b,cmit eFassung id_e, die Identität Morphismus e. Es ist jetzt Baufschlussreich zu beobachten, dass in unserem Fall von Interesse, wo sich die Kategorie der Endofunktoren Xmit natürlichen Transformationen als Morphismen, *die Funktorkomposition und eder Identitätsfunktor befindet, alle diese Gesetze erfüllt sind, wie direkt überprüft werden kann.

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

Monoide in monoidalen Kategorien

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

Ein Monoid cin einer monoidalen Kategorie (B, *, e)ist ein Objekt Bmit 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, bei denen es sich um natürliche Transformationen handelt, die genau joinund returnfür eine Monade entsprechen. Die Verbindung wird noch deutlicher, wenn wir die Komposition deutlicher machen *und c * cdurch ersetzen c^2, wo csich unsere Monade befindet.

Beachten Sie schließlich, dass die 3 kommutativen Diagramme (in der Definition eines Monoids in einer monoidalen Kategorie) für allgemeine (nicht strenge) monoidale Kategorien geschrieben sind, während in unserem Fall alle natürlichen Transformationen, die als Teil der monoidalen Kategorie auftreten, tatsächlich Identitäten sind. Dadurch sind die Diagramme genau die gleichen wie in der Definition einer Monade, wodurch die Korrespondenz vollständig wird.

Fazit

Zusammenfassend ist jede Monade per Definition ein Endofunktor, daher ein Objekt in der Kategorie der Endofunktoren, wobei die Monade joinund die returnOperatoren die Definition eines Monoids in dieser bestimmten (strengen) monoidalen Kategorie erfüllen . Umgekehrt ist jedes Monoid in der monoidalen Kategorie der Endofunktoren per Definition ein Tripel, (c, mu, nu)das aus einem Objekt und zwei Pfeilen besteht, z. B. natürlichen Transformationen in unserem Fall, die die gleichen Gesetze wie eine Monade erfüllen.

Beachten Sie schließlich den Hauptunterschied zwischen den (klassischen) Monoiden und den allgemeineren Monoiden in monoidalen Kategorien. Die beiden Pfeile muund nuhöher sind keine binäre Operation und keine Einheit in einer Menge mehr. Stattdessen haben Sie einen festen Endofunktor c. Die Funktorkomposition *und der Identitätsfunktor allein bieten trotz dieser verwirrenden Bemerkung im Buch nicht die vollständige Struktur, die für die Monade benötigt wird.

Ein anderer Ansatz wäre, mit dem Standardmonoid Caller Selbstkarten einer Menge zu vergleichen A, wobei die binäre Operation die Zusammensetzung ist, in die das kartesische Standardprodukt abgebildet C x Cwerden kann C. Beim Übergang zum kategorisierten Monoid ersetzen wir das kartesische Produkt xdurch die Funktorkomposition *, und die binäre Operation wird durch die natürliche Transformation muvon c * cnach ersetzt c, dh eine Sammlung der joinOperatoren

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

für jedes Objekt T(Programmierung eingeben). Und die Identitätselemente in klassischen Monoiden, die mit Bildern von Karten aus einem festen Einpunktsatz identifiziert werden können, werden durch die Sammlung der returnOperatoren ersetzt

return: T->c(T) 

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

Dmitri Zaitsev
quelle
Was ist Ihre Antwort auf den Teil "Ist das wahr?" Der Frage? Stimmt es, dass eine Monade ein Monoid in der Kategorie der Endofunktoren ist? Und wenn ja, wie ist die Beziehung zwischen dem kategorietheoretischen Begriff eines Monoids und eines algebraischen Monoids (eine Menge mit einer assoziativen Multiplikation und einer Einheit)?
Alexander Belopolsky