Gibt es einen Nichtidentitäts-Monadenmorphismus M ~> M, der in M ​​monadisch natürlich ist?

8

Es ist bekannt, dass natürliche Transformationen mit Typensignatur a -> a Identitätsfunktionen sein müssen. Dies folgt aus dem Yoneda-Lemma, kann aber auch direkt abgeleitet werden. Diese Frage verlangt nach der gleichen Eigenschaft, aber nach Monadenmorphismen anstelle natürlicher Transformationen.

Betrachten Sie Monadenmorphismen M ~> Nzwischen Monaden. (Dies sind natürliche Transformationen M a -> N a, die die Monadenoperationen auf beiden Seiten bewahren. Diese Transformationen sind die Morphismen in der Kategorie der Monaden.) Wir können fragen, ob es einen Monadenmorphismus gibt e :: (Monad m) => m a -> m a, der für jede Monade auf die gleiche Weise funktioniert m. Mit anderen Worten, ein Monadenmorphismus emuss im Parameter des Monadentyps monadisch natürlich sein m.

Das monadische Natürlichkeitsgesetz besagt, dass wir für jeden Monadenmorphismus f: Ma -> Na zwischen zwei beliebigen Monaden M und N haben müssen f . e = e . f geeignete Typparameter haben müssen.

Die Frage ist, können wir beweisen, dass eine solche eeine Identitätsfunktion sein muss, oder gibt es ein Gegenbeispiel für einen Nichtidentitäts-Monadenmorphismus e, der als definiert ist

  e :: (Monad m) => m a -> m a
  e ma = ...

Ein fehlgeschlagener Versuch, dies zu definieren, eist:

 e ma = do
         _ <- ma
         x <- ma
         return x

Ein weiterer fehlgeschlagener Versuch ist

 e ma = do
         x <- ma
         _ <- ma
         return x

Beide Versuche haben die richtige Typensignatur, verfehlen jedoch die Monadenmorphismusgesetze.

Es scheint, dass das Yoneda-Lemma nicht auf diesen Fall angewendet werden kann, da es keine Monadenmorphismen gibt, in Unit ~> Mdenen Unitsich die Einheitsmonade befindet. Ich kann auch keinen Beweis direkt finden.

winitzki
quelle

Antworten:

2

Ich denke, Sie haben bereits alle interessanten Möglichkeiten ausgeschöpft. Jede Monad m => m a -> m aFunktion, die wir definieren könnten, sieht unweigerlich so aus:

e :: forall m a. Monad m => m a -> m a
e u = u >>= k
    where
    k :: a -> m a
    k = _

Insbesondere wenn k = return, e = id. Damit dies enicht der Fall ist id, kmuss es nicht u trivial verwendet werden (z. B. k = const uund entspricht k = flip fmap u . constIhren beiden Versuchen). In einem solchen Fall werden die uEffekte jedoch dupliziert, was edazu führt , dass es sich bei einer Reihe von Monadenoptionen nicht um einen Monadenmorphismus handelt m. Unter diesen Umständen ist der einzige vollständig polymorphe Monadenmorphismus in der Monadeid .


Lassen Sie uns das Argument deutlicher machen.

Der Klarheit halber werde ich für einen Moment zur join/ return/ fmapPräsentation wechseln . Wir wollen implementieren:

e :: forall m a. Monad m => m a -> m a
e u = _

Womit können wir die rechte Seite füllen? Die naheliegendste Wahl ist u. An sich bedeutet das e = id, was nicht interessant aussieht. Da wir jedoch auch haben join, returnund fmapes besteht die Möglichkeit , induktiv Argumentation, mit uals Basisfall. Nehmen wir an v :: m a, wir haben einige , die mit den Mitteln gebaut wurden, die wir zur Hand haben. Neben vsich haben wir folgende Möglichkeiten:

  1. join (return v), was vuns nichts Neues sagt und daher auch nichts Neues sagt;

  2. join (fmap return v), was auch ist v; und

  3. join (fmap (\x -> fmap (f x) w) v)für einige andere, w :: m adie nach unseren Regeln gebaut wurden, und einige f :: a -> a -> a. (Das Hinzufügen von mEbenen zu der Art von f, wie in a -> a -> m aund zusätzlichen joins, um sie zu entfernen, würde nirgendwohin führen, da wir dann die Herkunft dieser Ebenen nachweisen müssten, und die Dinge würden sich letztendlich auf die anderen Fälle reduzieren.)

Der einzig interessante Fall ist # 3. An dieser Stelle werde ich eine Abkürzung nehmen:

join (fmap (\x -> fmap (f x) w) v)
    = v >>= \x -> fmap (f x) w
    = f <$> v <*> w

Jede nicht urechte Seite kann daher in der Form ausgedrückt werden f <$> v <*> w, wobei vund wentweder eine uoder mehrere Iterationen dieses Musters sind und schließlich us an den Blättern erreichen. Anwendbare Ausdrücke dieser Art haben jedoch eine kanonische Form, die durch Verwendung der anwendbaren Gesetze erhalten wird, um alle Verwendungen von (<*>)links neu zuzuordnen , was in diesem Fall so aussehen muss ...

c <$> u <*> ... <*> u

... wobei die Ellipse für null oder mehr weitere Vorkommen von ugetrennt <*>steht und ceine a -> ... -> a -> aFunktion angemessener Arität ist. Da aes vollständig polymorph ist, cmuss es aufgrund seiner Parametrizität eine constähnliche Funktion sein, die eines seiner Argumente auswählt. Unter diesen Umständen kann jeder solche Ausdruck in Bezug auf (<*)und (*>)...

u *> ... <* u

... wobei die Ellipse für null oder mehr weitere Vorkommen von ugetrennt durch entweder *>oder steht <*, da *>rechts von a kein Nein steht <*.

Zurück zum Start: Alle idImplementierungen , die keine Kandidaten sind, müssen folgendermaßen aussehen:

e u = u *> ... <* u

Wir wollen eauch ein Monadenmorphismus sein. Infolgedessen muss es sich auch um einen anwendbaren Morphismus handeln. Bestimmtes:

-- (*>) = (>>) = \u v -> u >>= \_ -> v
e (u *> v) = e u *> e v

Das ist:

(u *> v) *> ... <* (u >* v) = (u *> ... <* u) *> (v *> ... <* v)

Wir haben jetzt einen klaren Weg zu einem Gegenbeispiel. Wenn wir die anwendbaren Gesetze verwenden, um beide Seiten in die kanonische Form umzuwandeln, werden wir (noch) verschachtelte us und vs auf der linken Seite und alle vs nach allen us auf der rechten Seite haben. Das bedeutet, dass das Anwesen nicht für Monaden wie geeignet istIO , Stateoder Writer, unabhängig davon , wie viele (*>)und (<*)es gibt in e, oder genau , welche Werte werden von den aufgenommenen const-ähnliche Funktionen auf beiden Seiten. Eine kurze Demo:

GHCi> e u = u *> u <* u  -- Canonical form: const const <$> u <*> u <*> u
GHCi> e (print 1 *> print 2)
1
2
1
2
1
2
GHCi> e (print 1) *> e (print 2)
1
1
1
2
2
2
Duplode
quelle
Ich kann keinen hinreichend strengen Beweis finden. Wie können wir beweisen , dass die Auswirkungen uwerden zwangsläufig , es sei denn dupliziert e = id? (Wir könnten auch schreibene u = do _ <- u; _ <- u; _ <- u; u weitere uEffekte und kombinieren .) Wie können wir mathematisch beschreiben, dass "ein monadischer Wert p :: m amehrere Effekte hat, von denen kopiert wurde u :: m a? Und wie können wir dann beweisen, dass doppelte (dreifache usw.) uEffekte notwendigerweise zu Verstößen gegen führen."
Monadenmorphismusgesetze
@winitzki Ich habe mein Argument expliziter niedergeschrieben. Der einzige Gedanke, den ich in der ursprünglichen Überarbeitung der Antwort sicherlich begangen hatte, war die Erwähnung von Idempotenz, da die von mir beobachteten Fehler mehr mit der Kommutativität von Effekten zu tun haben.
Duplode
Das ist interessant. Ich werde noch etwas darüber nachdenken müssen. Wie können wir beweisen, dass es nur einen Weg gibt, ein Nicht-Triviales zu implementieren e u, nämlich einen Ausdruck des u *> ... <* uvon Ihnen beschriebenen Formulars zu verwenden? Warum können wir keine andere clevere und komplizierte Kombination finden?fmap , returnund join, so dass wir etwas anderes bekommen? Es ist auch ein guter Schritt, anwendbare Morphismen zu berücksichtigen. Es könnte einfacher sein, die analoge Eigenschaft für anwendbare Morphismen zu beweisen als für Monadenmorphismen. (Die einzigen anwendungsbezogenen Morphismen, die anwendungsmäßig natürlich sind, sind Identitätsmorphismen?)
winitzki
@winitzki (1) Obwohl es schön wäre, eine kristallinere Präsentation zu haben (ich denke immer noch darüber nach), glaube ich, dass meine drei Fälle erschöpfend sind. Nur join _kann zu einem Nicht- idErgebnis führen, und # 3 ist der einzige Weg, der nicht zu einem idunendlichen Rückschritt führt. (2) Ein Applicative: Informell, wenn Ihr einziger Kleisli-Pfeil ist return, verbrauchen Sie nicht die zusätzliche KraftMonad , die Sie mitbringen, also können Sie genauso gut damit arbeiten Applicative. (3) Ja, die analoge Eigenschaft gilt für anwendbare Morphismen. Der Teil meiner Argumentation, der mit der in sich geschlossenen kanonischen Form beginnt, sollte als Beweis ausreichen.
Duplode
Wenn wir einen Monadenmorphismus hätten, der monadisch natürlich ist, hätten wir auch einen anwendungsbezogenen Morphismus, der anwendungsmäßig natürlich ist. Ich denke, es könnte einfacher sein zu beweisen, dass es keinen solchen anwendbaren Morphismus gibt.
Winitzki