Es ist bekannt, dass anwendungsbezogene Funktoren unter Komposition geschlossen sind, Monaden jedoch nicht. Ich hatte jedoch Probleme, ein konkretes Gegenbeispiel zu finden, das zeigt, dass Monaden nicht immer komponieren.
Diese Antwort gibt [String -> a]
als Beispiel eine Nicht-Monade. Nachdem ich ein bisschen damit herumgespielt habe, glaube ich es intuitiv, aber diese Antwort sagt nur "Join kann nicht implementiert werden", ohne wirklich eine Begründung zu geben. Ich hätte gerne etwas Formaleres. Natürlich gibt es viele Funktionen mit Typ [String -> [String -> a]] -> [String -> a]
; man muss zeigen, dass eine solche Funktion notwendigerweise nicht den Monadengesetzen entspricht.
Jedes Beispiel (mit beiliegendem Beweis) reicht aus; Ich suche nicht unbedingt nach einem Beweis für das obige Beispiel.
quelle
join
für die Komposition von zwei Monaden in zu schreiben allgemein . Dies führt jedoch zu keinen konkreten Beispielen.Antworten:
Betrachten Sie diese Monade, die zur
(Bool ->)
Monade isomorph ist :und komponiere es mit der
Maybe
Monade:Ich behaupte, das
Bad
kann keine Monade sein.Teilnachweis:
Es gibt nur einen Weg zu definieren
fmap
, der erfülltfmap id = id
:Erinnern Sie sich an die Monadengesetze:
Für die Definition von
return x
haben wir zwei Möglichkeiten:B Nothing
oderB (Just (P x x))
. Es ist klar , dass wir, um Hoffnung auf eine Rückkehrx
von (1) und (2) zu haben, nicht wegwerfen könnenx
, also müssen wir die zweite Option wählen.Das geht
join
. Da es nur wenige mögliche Eingaben gibt, können wir für jede einen Fall machen:Da der Ausgangstyp hat
Bad a
, sind die einzigen OptionenB Nothing
oderB (Just (P y1 y2))
woy1
,y2
müssen ausgewählt werdenx1 ... x4
.In den Fällen (A) und (B) haben wir keine Werte vom Typ
a
, daher müssen wir zurückkehrenB Nothing
in beiden Fällen zurückkehren.Fall (E) wird durch die Monadengesetze (1) und (2) bestimmt:
Um
B (Just (P y1 y2))
in Fall (E) zurückzukehren, bedeutet dies, dass wiry1
entwederx1
oder oderx3
undy2
entwederx2
oder auswählen müssenx4
.Ebenso heißt es, dass wir
y1
entwederx1
oder oderx2
undy2
entwederx3
oder auswählen müssenx4
. Wenn wir beide kombinieren, bestimmen wir, dass die rechte Seite von (E) sein mussB (Just (P x1 x4))
.Bisher ist alles gut, aber das Problem tritt auf, wenn Sie versuchen, die rechten Seiten für (C) und (D) auszufüllen.
Es gibt jeweils 5 mögliche rechte Seiten, und keine der Kombinationen funktioniert. Ich habe noch kein gutes Argument dafür, aber ich habe ein Programm, das alle Kombinationen ausführlich testet:
quelle
swap :: Pair (Maybe a) -> Maybe (Pair a)
.(Maybe a, Maybe a)
ist eine Monade (weil es ein Produkt von zwei Monaden ist), aberMaybe (a, a)
keine Monade. Ich habe auchMaybe (a,a)
durch explizite Berechnungen bestätigt, dass dies keine Monade ist.Maybe (a, a)
es keine Monade ist. Sowohl Maybe als auch Tuple sind verfahrbar und sollten in beliebiger Reihenfolge zusammensetzbar sein. Es gibt auch andere SO-Fragen, die sich mit diesem speziellen Beispiel befassen.Betrachten Sie für ein kleines konkretes Gegenbeispiel die Terminal-Monade.
Das
return
und>>=
geh einfachThud
, und die Gesetze gelten trivial.Lassen Sie uns jetzt auch die Writer-Monade für Bool haben (mit beispielsweise der Xor-Monoid-Struktur).
Ähm, wir brauchen Komposition
Versuchen Sie nun zu definieren ...
Die Parametrizität sagt uns, dass
???
dies in keiner nützlichen Weise davon abhängen kannx
, also muss es eine Konstante sein. Infolgedessenjoin . return
ist notwendigerweise auch eine konstante Funktion, daher das Gesetzmuss für welche Definitionen auch immer scheitern
join
undreturn
wir wählen.quelle
Ausgeschlossene Mitte konstruieren
(->) r
ist eine Monade für jedenr
undEither e
ist eine Monade für jedene
. Definieren wir ihre Zusammensetzung ((->) r
innen,Either e
außen):Ich behaupte , dass , wenn
Comp r e
eine Monade für alle warenr
unde
dann konnten wir erkennen , das Gesetz der exluded Mitte . Dies ist in der intuitionistischen Logik , die Typensystemen funktionaler Sprachen zugrunde liegt, nicht möglich (das Gesetz der ausgeschlossenen Mitte entspricht dem Aufruf / cc- Operator).Nehmen wir an, es
Comp
ist eine Monade. Dann haben wirund so können wir definieren
(Dies ist nur die
swap
Funktion aus Papier. Monaden komponieren, die Brent erwähnt, Abschn. 4.3, nur mit hinzugefügten (De-) Konstruktoren von Newtype. Beachten Sie, dass es uns egal ist, welche Eigenschaften es hat. Das einzig Wichtige ist, dass es definierbar und vollständig ist .)Jetzt lasst uns einstellen
und spezialisieren Swap für
r = b
,e = b
,a = False
:Fazit: Obwohl
(->) r
undEither r
sind Monaden, kann ihre ZusammensetzungComp r r
nicht sein.Hinweis: Dass dies auch, wie reflektiert
ReaderT
undEitherT
definiert. BeideReaderT r (Either e)
undEitherT e (Reader r)
sind isomorph zur -> Either e a
! Es gibt keine Möglichkeit, eine Monade für das Duale zu definierenEither e (r -> a)
.Austretende
IO
AktionenEs gibt viele Beispiele in der gleichen Richtung,
IO
die dazu führen undIO
irgendwie zur Flucht führen . Beispielsweise:Jetzt lass uns haben
Was passiert, wenn dieses Programm ausgeführt wird? Es gibt zwei Möglichkeiten:
input
von der Konsole gelesen haben. Dies bedeutet, dass die Reihenfolge der Aktionen umgekehrt wurde und die Aktionen von "foo
Escape" in "Pure" umgewandelt wurdenf
.Oder
swap
(daherjoin
) wirft dieIO
Aktion weg und weder "Erste" noch "Zweite" werden jemals gedruckt. Dies bedeutet jedoch, dass diesjoin
gegen das Gesetz verstößtdenn wenn
join
wirft dieIO
Aktion weg, dannAndere ähnliche
IO
+ Monadenkombinationen führen zur KonstruktionEntweder müssen ihre
join
Implementierungen dase
Entkommen erlaubenIO
oder sie müssen es wegwerfen und durch etwas anderes ersetzen, was gegen das Gesetz verstößt.quelle
<*>
stattdessen sein), habe versucht, es zu bearbeiten, aber mir wurde gesagt, dass meine Bearbeitung zu kurz war.) --- Es ist nicht klar, um Ich, dass eine Definition für eine Definition fürjoin
impliziertswap
. Könnten Sie es erweitern? Das Papier bezeichnet Brent scheint zu implizieren , von zu gehen ,join
umswap
wir die folgenden Annahmen müssen:joinM . fmapM join = join . joinM
undjoin . fmap (fmapM joinN ) = fmapM joinN . join
wo joinM = beitreten :: M, usw.swap
um sie an das Papier anzupassen ). Ich habe das Papier bis jetzt nicht überprüft, und Sie haben Recht, es sieht so aus, als ob wir J (1) und J (2) brauchen, umswap
<-> zu definierenjoin
. Dies ist vielleicht eine Schwachstelle meines Beweises und ich werde mehr darüber nachdenken (vielleicht wäre es möglich, etwas daraus zu ziehen, dass es so istApplicative
).join
, könnten wirswap :: (Int -> Maybe a) -> Maybe (Int -> a)
anhand der obigen Definition definieren (unabhängig davon, welche Gesetze diesswap
erfüllt). Wie würde sich so etwasswap
verhalten? Wenn dies nicht der Fall istInt
, muss es nichts an sein Argument weitergeben, sodass esNothing
für alle Eingaben zurückkehren muss. Ich glaube, wir können einen Widerspruch fürjoin
die Monadengesetze bekommen, ohnejoin
vonswap
hinten definieren zu müssen . Ich werde es überprüfen und dich wissen lassen.Ihr Link verweist auf diesen Datentyp. Versuchen wir also, eine bestimmte Implementierung auszuwählen:
data A3 a = A3 (A1 (A2 a))
Ich werde willkürlich auswählen
A1 = IO, A2 = []
. Wir werden es auchnewtype
zum Spaß zu einem besonders spitzen Namen machen:newtype ListT IO a = ListT (IO [a])
Lassen Sie uns eine beliebige Aktion in diesem Typ entwickeln und sie auf zwei verschiedene, aber gleiche Arten ausführen:
Wie Sie sehen, verstößt dies gegen das Assoziativitätsgesetz :
∀x y z. (x >=> y) >=> z == x >=> (y >=> z)
.Es stellt sich heraus,
ListT m
ist nur eine Monade, wennm
es sich um eine kommutative Monade handelt. Dies verhindert, dass eine große Kategorie von Monaden komponiert[]
, was gegen die universelle Regel verstößt, dass "das Komponieren von zwei beliebigen Monaden eine Monade ergibt".Siehe auch: https://stackoverflow.com/a/12617918/1769569
quelle
ListT
nicht in allen Fällen eine Monade erzeugt, anstatt zu zeigen, dass keine mögliche Definition funktionieren kann.Monad
Instanz fürListT
und eine Demonstration, dass es keine anderen gibt. Die Aussage ist "für all das gibt es das" und so ist die Negation "es gibt das so, dass für all das"Monaden komponieren nicht. Nicht generisch - es gibt keine allgemeine Möglichkeit, Monaden zu komponieren. Siehe https://www.slideshare.net/pjschwarz/monads-do-not-compose
quelle