Konkretes Beispiel, das zeigt, dass Monaden unter Komposition nicht geschlossen sind (mit Beweis)?

82

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.

Brent Yorgey
quelle
Der nächste, den ich finden kann, ist der Anhang von web.cecs.pdx.edu/~mpj/pubs/RR-1004.pdf , der zeigt, dass es unter vielen vereinfachenden Annahmen unmöglich ist, joinfür die Komposition von zwei Monaden in zu schreiben allgemein . Dies führt jedoch zu keinen konkreten Beispielen.
Brent Yorgey
Möglicherweise erhalten Sie bessere Antworten auf diese Frage auf cs.stackexchange.com, der neuen Website für Computer Science Stack Exchange.
Patrick87
3
Vielleicht verstehe ich nicht, aber ich denke, die Frage könnte genauer definiert werden. Wenn Sie sagen, dass zwei Monaden "komponiert" werden, meinen Sie damit einfach das Komponieren der Typkonstruktoren? Und wenn das Ergebnis "keine Monade ist", bedeutet dies, dass eine Monadeninstanz dieses Typkonstruktors nicht geschrieben werden kann? Und wenn eine Monadeninstanz für den zusammengesetzten Typkonstruktor geschrieben werden kann, muss sie in irgendeiner Beziehung zu den Instanzen der beiden Faktormonaden stehen oder kann sie völlig unabhängig sein?
Owen
1
Ja, ich meine das Komponieren der Typkonstruktoren; "keine Monade" bedeutet, dass eine gültige (rechtmäßige) Monadeninstanz nicht geschrieben werden kann; und es ist mir egal, ob die Instanz für die Komposition irgendeine Beziehung zu den Instanzen der Faktoren hat.
Brent Yorgey

Antworten:

42

Betrachten Sie diese Monade, die zur (Bool ->)Monade isomorph ist :

data Pair a = P a a

instance Functor Pair where
  fmap f (P x y) = P (f x) (f y)

instance Monad Pair where
  return x = P x x
  P a b >>= f = P x y
    where P x _ = f a
          P _ y = f b

und komponiere es mit der MaybeMonade:

newtype Bad a = B (Maybe (Pair a))

Ich behaupte, das Badkann keine Monade sein.


Teilnachweis:

Es gibt nur einen Weg zu definieren fmap, der erfüllt fmap id = id:

instance Functor Bad where
    fmap f (B x) = B $ fmap (fmap f) x

Erinnern Sie sich an die Monadengesetze:

(1) join (return x) = x 
(2) join (fmap return x) = x
(3) join (join x) = join (fmap join x)

Für die Definition von return xhaben wir zwei Möglichkeiten: B Nothingoder B (Just (P x x)). Es ist klar , dass wir, um Hoffnung auf eine Rückkehr xvon (1) und (2) zu haben, nicht wegwerfen können x, also müssen wir die zweite Option wählen.

return' :: a -> Bad a
return' x = B (Just (P x x))

Das geht join. Da es nur wenige mögliche Eingaben gibt, können wir für jede einen Fall machen:

join :: Bad (Bad a) -> Bad a
(A) join (B Nothing) = ???
(B) join (B (Just (P (B Nothing)          (B Nothing))))          = ???
(C) join (B (Just (P (B (Just (P x1 x2))) (B Nothing))))          = ???
(D) join (B (Just (P (B Nothing)          (B (Just (P x1 x2)))))) = ???
(E) join (B (Just (P (B (Just (P x1 x2))) (B (Just (P x3 x4)))))) = ???

Da der Ausgangstyp hat Bad a, sind die einzigen Optionen B Nothingoder B (Just (P y1 y2))wo y1, y2mü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:

-- apply (1) to (B (Just (P y1 y2)))
join (return' (B (Just (P y1 y2))))
= -- using our definition of return'
join (B (Just (P (B (Just (P y1 y2))) (B (Just (P y1 y2))))))
= -- from (1) this should equal
B (Just (P y1 y2))

Um B (Just (P y1 y2))in Fall (E) zurückzukehren, bedeutet dies, dass wir y1entweder x1oder oder x3und y2entweder x2oder auswählen müssen x4.

-- apply (2) to (B (Just (P y1 y2)))
join (fmap return' (B (Just (P y1 y2))))
= -- def of fmap
join (B (Just (P (return y1) (return y2))))
= -- def of return
join (B (Just (P (B (Just (P y1 y1))) (B (Just (P y2 y2))))))
= -- from (2) this should equal
B (Just (P y1 y2))

Ebenso heißt es, dass wir y1entweder x1oder oder x2und y2entweder x3oder auswählen müssen x4. Wenn wir beide kombinieren, bestimmen wir, dass die rechte Seite von (E) sein muss B (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:

{-# LANGUAGE ImpredicativeTypes, ScopedTypeVariables #-}

import Control.Monad (guard)

data Pair a = P a a
  deriving (Eq, Show)

instance Functor Pair where
  fmap f (P x y) = P (f x) (f y)

instance Monad Pair where
  return x = P x x
  P a b >>= f = P x y
    where P x _ = f a
          P _ y = f b

newtype Bad a = B (Maybe (Pair a))
  deriving (Eq, Show)

instance Functor Bad where
  fmap f (B x) = B $ fmap (fmap f) x

-- The only definition that could possibly work.
unit :: a -> Bad a
unit x = B (Just (P x x))

-- Number of possible definitions of join for this type. If this equals zero, no monad for you!
joins :: Integer
joins = sum $ do
  -- Try all possible ways of handling cases 3 and 4 in the definition of join below.
  let ways = [ \_ _ -> B Nothing
             , \a b -> B (Just (P a a))
             , \a b -> B (Just (P a b))
             , \a b -> B (Just (P b a))
             , \a b -> B (Just (P b b)) ] :: [forall a. a -> a -> Bad a]
  c3 :: forall a. a -> a -> Bad a <- ways
  c4 :: forall a. a -> a -> Bad a <- ways

  let join :: forall a. Bad (Bad a) -> Bad a
      join (B Nothing) = B Nothing -- no choice
      join (B (Just (P (B Nothing) (B Nothing)))) = B Nothing -- again, no choice
      join (B (Just (P (B (Just (P x1 x2))) (B Nothing)))) = c3 x1 x2
      join (B (Just (P (B Nothing) (B (Just (P x3 x4)))))) = c4 x3 x4
      join (B (Just (P (B (Just (P x1 x2))) (B (Just (P x3 x4)))))) = B (Just (P x1 x4)) -- derived from monad laws

  -- We've already learnt all we can from these two, but I decided to leave them in anyway.
  guard $ all (\x -> join (unit x) == x) bad1
  guard $ all (\x -> join (fmap unit x) == x) bad1

  -- This is the one that matters
  guard $ all (\x -> join (join x) == join (fmap join x)) bad3

  return 1 

main = putStrLn $ show joins ++ " combinations work."

-- Functions for making all the different forms of Bad values containing distinct Ints.

bad1 :: [Bad Int]
bad1 = map fst (bad1' 1)

bad3 :: [Bad (Bad (Bad Int))]
bad3 = map fst (bad3' 1)

bad1' :: Int -> [(Bad Int, Int)]
bad1' n = [(B Nothing, n), (B (Just (P n (n+1))), n+2)]

bad2' :: Int -> [(Bad (Bad Int), Int)]
bad2' n = (B Nothing, n) : do
  (x, n')  <- bad1' n
  (y, n'') <- bad1' n'
  return (B (Just (P x y)), n'')

bad3' :: Int -> [(Bad (Bad (Bad Int)), Int)]
bad3' n = (B Nothing, n) : do
  (x, n')  <- bad2' n
  (y, n'') <- bad2' n'
  return (B (Just (P x y)), n'')
Hammar
quelle
Danke, ich bin überzeugt! Ich frage mich jedoch, ob es Möglichkeiten gibt, Ihren Beweis zu vereinfachen.
Brent Yorgey
1
@BrentYorgey: Ich vermute, dass dies der Fall sein sollte, da die Probleme mit den Fällen (C) und (D) den Problemen, die Sie beim Definieren haben, sehr ähnlich zu sein scheinen swap :: Pair (Maybe a) -> Maybe (Pair a).
Hammar
11
Kurz gesagt: Monaden dürfen Informationen wegwerfen, und das ist in Ordnung, wenn sie nur in sich selbst verschachtelt sind. Wenn Sie jedoch eine Monade zur Erhaltung von Informationen und eine Monade zum Löschen von Informationen haben, kombinieren Sie die beiden Informationen, obwohl die Informationen, die Informationen erhalten , diese Informationen benötigen , um ihre eigenen Monadengesetze zu erfüllen. Sie können also keine beliebigen Monaden kombinieren. (Aus diesem Grund benötigen Sie Traversable-Monaden, die garantieren, dass sie keine relevanten Informationen löschen. Sie sind willkürlich zusammensetzbar.) Vielen Dank für die Intuition!
Xanthir
@Xanthir Composing funktioniert nur in einer Reihenfolge: (Maybe a, Maybe a)ist eine Monade (weil es ein Produkt von zwei Monaden ist), aber Maybe (a, a)keine Monade. Ich habe auch Maybe (a,a)durch explizite Berechnungen bestätigt, dass dies keine Monade ist.
Winitzki
Es macht etwas aus zu zeigen, warum 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.
Xanthir
38

Betrachten Sie für ein kleines konkretes Gegenbeispiel die Terminal-Monade.

data Thud x = Thud

Das returnund >>=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).

data Flip x = Flip Bool x

instance Monad Flip where
   return x = Flip False x
   Flip False x  >>= f = f x
   Flip True x   >>= f = Flip (not b) y where Flip b y = f x

Ähm, wir brauchen Komposition

newtype (:.:) f g x = C (f (g x))

Versuchen Sie nun zu definieren ...

instance Monad (Flip :.: Thud) where  -- that's effectively the constant `Bool` functor
  return x = C (Flip ??? Thud)
  ...

Die Parametrizität sagt uns, dass ???dies in keiner nützlichen Weise davon abhängen kann x, also muss es eine Konstante sein. Infolgedessen join . returnist notwendigerweise auch eine konstante Funktion, daher das Gesetz

join . return = id

muss für welche Definitionen auch immer scheitern joinund returnwir wählen.

Schweinearbeiter
quelle
3
Auf Carlos Hamalainen-Blog gibt es eine zusätzliche, sehr klare und detaillierte Analyse der obigen Antwort, die ich hilfreich fand: carlo-hamalainen.net/blog/2014/1/2/…
paluh
34

Ausgeschlossene Mitte konstruieren

(->) rist eine Monade für jeden rund Either eist eine Monade für jeden e. Definieren wir ihre Zusammensetzung ( (->) rinnen, Either eaußen):

import Control.Monad
newtype Comp r e a = Comp { uncomp :: Either e (r -> a) }

Ich behaupte , dass , wenn Comp r eeine Monade für alle waren rund edann 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 Compist eine Monade. Dann haben wir

join :: Comp r e (Comp r e a) -> Comp r e a

und so können wir definieren

swap :: (r -> Either e a) -> Either e (r -> a)
swap = uncomp . join . Comp . return . liftM (Comp . liftM return)

(Dies ist nur die swapFunktion 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

data False -- an empty datatype corresponding to logical false
type Neg a = (a -> False) -- corresponds to logical negation

und spezialisieren Swap für r = b, e = b, a = False:

excludedMiddle :: Either b (Neg b)
excludedMiddle = swap Left

Fazit: Obwohl (->) rund Either rsind Monaden, kann ihre Zusammensetzung Comp r rnicht sein.

Hinweis: Dass dies auch, wie reflektiert ReaderTund EitherTdefiniert. Beide ReaderT r (Either e) und EitherT e (Reader r)sind isomorph zu r -> Either e a! Es gibt keine Möglichkeit, eine Monade für das Duale zu definieren Either e (r -> a).


Austretende IOAktionen

Es gibt viele Beispiele in der gleichen Richtung, IOdie dazu führen und IOirgendwie zur Flucht führen . Beispielsweise:

newtype Comp r a = Comp { uncomp :: IO (r -> a) }

swap :: (r -> IO a) -> IO (r -> a)
swap = uncomp . join . Comp . return . liftM (Comp . liftM return)

Jetzt lass uns haben

main :: IO ()
main = do
   let foo True  = print "First" >> return 1
       foo False = print "Second" >> return 2
   f <- swap foo
   input <- readLn
   print (f input)

Was passiert, wenn dieses Programm ausgeführt wird? Es gibt zwei Möglichkeiten:

  1. "First" oder "Second" wird gedruckt, nachdem wir inputvon der Konsole gelesen haben. Dies bedeutet, dass die Reihenfolge der Aktionen umgekehrt wurde und die Aktionen von " fooEscape" in "Pure" umgewandelt wurden f.
  2. Oder swap(daher join) wirft die IOAktion weg und weder "Erste" noch "Zweite" werden jemals gedruckt. Dies bedeutet jedoch, dass dies joingegen das Gesetz verstößt

    join . return = id

    denn wenn joinwirft die IOAktion weg, dann

    foo  (join . return) foo

Andere ähnliche IO+ Monadenkombinationen führen zur Konstruktion

swapEither :: IO (Either e a) -> Either e (IO a)
swapWriter :: (Monoid e) => IO (Writer e a) -> Writer e (IO a)
swapState  :: IO (State e a) -> State e (IO a)
...

Entweder müssen ihre joinImplementierungen das eEntkommen erlauben IOoder sie müssen es wegwerfen und durch etwas anderes ersetzen, was gegen das Gesetz verstößt.

Petr Pudlák
quelle
(Ich nehme an, "ap" ist ein Tippfehler in "wo fmap, pure und ap die kanonischen Definitionen sind" (sollte <*>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ür joinimpliziert swap. Könnten Sie es erweitern? Das Papier bezeichnet Brent scheint zu implizieren , von zu gehen , joinum swapwir die folgenden Annahmen müssen: joinM . fmapM join = join . joinMund join . fmap (fmapM joinN ) = fmapM joinN . join wo joinM = beitreten :: M, usw.
Rafael Caetano
1
@ RafaelCaetano Danke für den Tippfehler, ich habe ihn behoben (und auch die Funktion umbenannt, swapum 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, um swap<-> zu definieren join. 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 ist Applicative).
Petr Pudlák
@ RafaelCaetano Aber ich glaube, der Beweis ist immer noch gültig: Wenn wir das hätten join, könnten wir swap :: (Int -> Maybe a) -> Maybe (Int -> a)anhand der obigen Definition definieren (unabhängig davon, welche Gesetze dies swaperfüllt). Wie würde sich so etwas swapverhalten? Wenn dies nicht der Fall ist Int, muss es nichts an sein Argument weitergeben, sodass es Nothingfür alle Eingaben zurückkehren muss. Ich glaube, wir können einen Widerspruch für joindie Monadengesetze bekommen, ohne joinvon swaphinten definieren zu müssen . Ich werde es überprüfen und dich wissen lassen.
Petr Pudlák
@Petr: So wie es aussieht, stimme ich Rafael zu, dass dies nicht ganz der Beweis ist, den ich suche, aber ich bin auch neugierig zu sehen, ob es in der von Ihnen erwähnten Weise repariert werden kann.
Brent Yorgey
1
@ PetrPudlák Wow, sehr schön! Ja, ich kaufe es jetzt total. Dies sind einige wirklich interessante Erkenntnisse. Ich hätte nicht gedacht, dass die bloße Möglichkeit, einen Tausch zu konstruieren , zu einem Widerspruch führen könnte, ohne auf eines der Monadengesetze Bezug zu nehmen! Wenn ich mehrere Antworten akzeptieren könnte, würde ich auch diese akzeptieren.
Brent Yorgey
4

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 auch newtypezum 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:

λ> let v n = ListT $ do {putStr (show n); return [0, 1]}
λ> runListT $ ((v >=> v) >=> v) 0
0010101[0,1,0,1,0,1,0,1]
λ> runListT $ (v >=> (v >=> v)) 0
0001101[0,1,0,1,0,1,0,1]

Wie Sie sehen, verstößt dies gegen das Assoziativitätsgesetz : ∀x y z. (x >=> y) >=> z == x >=> (y >=> z).

Es stellt sich heraus, ListT mist nur eine Monade, wenn mes 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

hpc
quelle
11
Ich würde denken, dass dies nur zeigt, dass eine bestimmte Definition von ListTnicht in allen Fällen eine Monade erzeugt, anstatt zu zeigen, dass keine mögliche Definition funktionieren kann.
CA McCann
Ich muss nicht Die Negation von "für all das, das" ist "es gibt ein Gegenbeispiel". Die Frage lautete: "Für alle Monaden bildet ihre Zusammensetzung eine Monade." Ich habe eine Kombination von Typen gezeigt, die für sich genommen Monaden sind, aber nicht komponieren können.
HPC
11
@hpc, aber die Zusammensetzung von zwei Monaden ist mehr als die Zusammensetzung ihrer Typen. Sie brauchen auch die Operationen, und meine Interpretation von Brents Frage ist, dass es möglicherweise keinen methodischen Weg gibt, um die Implementierung der Operationen abzuleiten - er sucht nach etwas noch Stärkerem, dass einige Kompositionen keine Operationen haben, die den Gesetzen entsprechen, ob mechanisch ableitbar oder nicht. Ist das sinnvoll?
Luqui
Ja, Luqui hat es richtig. Entschuldigung, wenn meine ursprüngliche Frage nicht klar war.
Brent Yorgey
Was in dieser Antwort wirklich fehlt, ist die MonadInstanz für ListTund 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"
Ben Millwood