Konkretny przykład pokazujący, że monady nie są zamknięte w kompozycji (z dowodem)?

82

Powszechnie wiadomo, że funktory aplikacyjne są zamknięte w kompozycji, ale monady nie. Jednak mam problem ze znalezieniem konkretnego kontrprzykładu pokazującego, że monady nie zawsze komponują.

Ta odpowiedź daje [String -> a]jako przykład nie-monady. Po trochę zabawie z tym, wierzę w to intuicyjnie, ale ta odpowiedź mówi tylko, że „złączenia nie można zaimplementować” bez podania żadnego uzasadnienia. Chciałbym coś bardziej formalnego. Oczywiście istnieje wiele funkcji z typem [String -> [String -> a]] -> [String -> a]; trzeba wykazać, że jakakolwiek taka funkcja niekoniecznie spełnia prawa monady.

Dowolny przykład (z towarzyszącym dowodem) wystarczy; Niekoniecznie szukam w szczególności dowodu na powyższy przykład.

Brent Yorgey
źródło
Najbliższy, jaki udało mi się znaleźć, to załącznik web.cecs.pdx.edu/~mpj/pubs/RR-1004.pdf , z którego wynika, że ​​przy wielu upraszczających założeniach nie da się napisać joindla kompozycji dwóch monad w ogólne . Ale to nie prowadzi do żadnych konkretnych przykładów.
Brent Yorgey
Możesz uzyskać lepsze odpowiedzi na to pytanie na cs.stackexchange.com, nowej witrynie Computer Science Stack Exchange.
Patrick87,
3
Może nie rozumiem, ale myślę, że pytanie można by precyzyjniej zdefiniować. Kiedy mówisz „komponowanie” dwóch monad, czy masz na myśli po prostu komponowanie konstruktorów typów? A kiedy wynik „nie jest monadą”, czy oznacza to, że instancja monady tego typu konstrukcji nie może zostać zapisana? A jeśli można napisać instancję monady dla konstruktora typu złożonego, czy musi ona mieć jakikolwiek związek z instancjami monad dwuskładnikowych, czy też może być całkowicie niezwiązana?
Owen
1
Tak, mam na myśli tworzenie konstruktorów typów; „nie monada” oznacza, że ​​nie można zapisać ważnej (zgodnej z prawem) instancji monady; i nie obchodzi mnie, czy instancja kompozycji ma jakikolwiek związek z instancjami czynników.
Brent Yorgey

Odpowiedzi:

42

Rozważ tę monadę, która jest izomorficzna z (Bool ->)monadą:

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

i skomponuj go z Maybemonadą:

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

Twierdzę, że Badto nie może być monada.


Częściowy dowód:

Jest tylko jeden sposób, aby określić fmap, który spełnia fmap id = id:

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

Przypomnij sobie prawa monady:

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

Aby zdefiniować return x, mamy dwie możliwości: B Nothinglub B (Just (P x x)). Jest jasne, że aby mieć jakąkolwiek nadzieję na powrót xz (1) i (2), nie możemy wyrzucić x, więc musimy wybrać drugą opcję.

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

To odchodzi join. Ponieważ istnieje tylko kilka możliwych danych wejściowych, możemy przedstawić przypadek dla każdego:

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)))))) = ???

Ponieważ dane wyjściowe mają typ Bad a, jedyne opcje to B Nothinglub B (Just (P y1 y2))gdzie y1, y2należy wybrać spośród x1 ... x4.

W przypadkach (A) i (B) nie mamy wartości typu a, więc B Nothingw obu przypadkach jesteśmy zmuszeni do zwrócenia .

Przypadek (E) jest określony przez prawa monady (1) i (2):

-- 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))

Aby powrócić B (Just (P y1 y2))w przypadku (E), oznacza to, że musimy wybrać y1albo x1albo x3, y2albo x2albo albo albo 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))

To samo mówi, że musimy wybierać y1spośród albo x1albo x2, albo , albo , y2albo, x3albo x4. Łącząc oba, ustalamy, że prawa strona (E) musi być B (Just (P x1 x4)).

Jak dotąd wszystko jest w porządku, ale problem pojawia się, gdy próbujesz wypełnić prawe strony dla (C) i (D).

Istnieje 5 możliwych prawych stron dla każdej i żadna z kombinacji nie działa. Nie mam jeszcze na to ładnego argumentu, ale mam program, który wyczerpująco testuje wszystkie kombinacje:

{-# 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
źródło
Dzięki, jestem przekonany! Chociaż to sprawia, że ​​zastanawiam się, czy istnieją sposoby na uproszczenie twojego dowodu.
Brent Yorgey,
1
@BrentYorgey: Podejrzewam, że powinno być, ponieważ problemy z przypadkami (C) i (D) wydają się być bardzo podobne do problemów, które masz, próbując zdefiniować swap :: Pair (Maybe a) -> Maybe (Pair a).
hammar
11
Krótko mówiąc: monady mogą wyrzucać informacje i to jest w porządku, jeśli są po prostu zagnieżdżone w sobie. Ale kiedy masz monadę zachowującą informacje i monadę upuszczającą informacje, połączenie tych dwóch upuszcza informacje, nawet jeśli jednostka zachowująca informacje potrzebuje tych informacji, aby spełnić własne prawa monady. Nie możesz więc łączyć dowolnych monad. (Dlatego potrzebujesz przemierzalnych monad, które gwarantują, że nie upuszczą istotnych informacji; można je dowolnie komponować). Dzięki za intuicję!
Xanthir
@Xanthir Komponowanie działa tylko w jednym porządku: (Maybe a, Maybe a)jest monadą (ponieważ jest produktem dwóch monad), ale Maybe (a, a)nie jest monadą. Potwierdziłem również, że Maybe (a,a)nie jest to monada przez wyraźne obliczenia.
winitzki,
Masz ochotę pokazać, dlaczego Maybe (a, a)nie jest monadą? Obie opcje, może i krotka, są przemienne i powinny być tworzone w dowolnej kolejności; istnieją inne pytania SO, które również dotyczą tego konkretnego przykładu.
Xanthir
38

Dla małego konkretnego kontrprzykładu rozważmy monadę terminalu.

data Thud x = Thud

returnI >>=po prostu pójść Thud, a prawa trzymać trywialnie.

Weźmy teraz również monadę pisarza dla Bool (z, powiedzmy, strukturą xor-monoid).

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

Eee, potrzebujemy kompozycji

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

Teraz spróbuj zdefiniować ...

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

Parametryczność mówi nam, że ???nie można od nich w żaden użyteczny sposób polegać x, więc musi być stałą. W rezultacie join . returnjest z konieczności również funkcją stałą, stąd prawo

join . return = id

musi zawieść dla jakichkolwiek definicji joini returnwybierzemy.

świniarz
źródło
3
Na blogu Carlo Hamalainen znajduje się dodatkowa, bardzo przejrzysta i szczegółowa analiza powyższej odpowiedzi, która okazała się pomocna: carlo-hamalainen.net/blog/2014/1/2/…
paluh
34

Konstruowanie wykluczonego środka

(->) rjest monadą dla każdego ri Either ejest monadą dla każdego e. Określmy ich skład ( (->) rwewnątrz, na Either ezewnątrz):

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

I twierdzą, że jeśli Comp r ebyły monada dla każdego ri ewtedy moglibyśmy zrealizować prawo nieobecny środku . Nie jest to możliwe w logice intuicjonistycznej, która leży u podstaw typosystemów języków funkcyjnych (posiadanie prawa wyłączonego środka jest równoznaczne z posiadaniem operatora wywołania / cc ).

Załóżmy, że Compjest to monada. Potem będzie

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

i tak możemy zdefiniować

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

(To tylko swapfunkcja z artykułu Tworzenie monad, o których wspomina Brent, sekcja 4.3, tylko z dodanymi (de) konstruktorami newtype. Zauważ, że nie obchodzi nas, jakie ma właściwości, jedyną ważną rzeczą jest to, że jest definiowalna i całkowita .)

Teraz zaczynajmy

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

i specjalizuje się na zamianę r = b, e = b, a = False:

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

Wniosek: chociaż są (->) ri Either rsą monadami, ich skład Comp r rnie może być.

Uwaga: znajduje to również odzwierciedlenie w sposobie ReaderTi sposobie EitherTdefiniowania. Zarówno ReaderT r (Either e) i EitherT e (Reader r)jest izomorficzna r -> Either e a! Nie ma sposobu, jak zdefiniować monadę dla dualności Either e (r -> a).


IODziałania ucieczki

Jest wiele przykładów w tym samym duchu, które obejmują IOi prowadzą do ucieczki IO. Na przykład:

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)

A teraz miejmy

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)

Co się stanie, gdy ten program zostanie uruchomiony? Istnieją dwie możliwości:

  1. „Pierwszy” i „drugi” jest drukowany po czytamy inputz konsoli, co oznacza, że sekwencja działań został odwrócony i że działania od foouciekł do czysta f.
  2. Lub swap(stąd join) odrzuca IOakcję i ani „Pierwszy”, ani „Drugi” nigdy nie są drukowane. Ale to oznacza, że joinnarusza prawo

    join . return = id
    

    ponieważ jeśli joinodrzuca IOdziałanie, to

    foo ≠ (join . return) foo
    

Inne podobne IOkombinacje + monada prowadzą do konstruowania

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)
...

Albo ich joinimplementacje muszą pozwolić ena ucieczkę, IOalbo muszą to wyrzucić i zastąpić czymś innym, łamiącym prawo.

Petr
źródło
(Przypuszczam, że „ap” to literówka w „gdzie fmap, pure i ap to definicje kanoniczne” (powinno być <*>zamiast tego), próbowałem go edytować, ale powiedziano mi, że moja edycja jest za krótka.) --- Nie jest jasne, czy mnie, że posiadanie definicji dla joinimplikuje definicję dla swap. Czy mógłbyś to rozwinąć? Artykuł, do którego odnosi się Brent wydaje się sugerować, że aby przejść od joindo swappotrzebujemy następujących założeń: joinM . fmapM join = join . joinMi join . fmap (fmapM joinN ) = fmapM joinN . join gdzie joinM = join :: M itd.
Rafael Caetano
1
@RafaelCaetano Dzięki za literówkę, poprawiłem to (i zmieniłem również nazwę funkcji swapna pasującą do papieru). Do tej pory nie sprawdzałem papieru i masz rację, wygląda na to, że potrzebujemy J (1) i J (2) do zdefiniowania swap<-> join. To chyba słaby punkt mojego dowodu i pomyślę o tym więcej (może dałoby się coś wyciągnąć z tego, że jest Applicative).
Petr
@RafaelCaetano Ale uważam, że dowód jest nadal ważny: gdybyśmy mieli join, moglibyśmy zdefiniować swap :: (Int -> Maybe a) -> Maybe (Int -> a)za pomocą powyższej definicji (bez względu na to, jakie prawa to swapspełnia). Jak taki by się swapzachowywał? Ponieważ nie Int, nie ma nic do przekazania do swojego argumentu, więc musiałby zwrócić Nothingwszystkie dane wejściowe. Wierzę, że możemy uzyskać sprzeczność z joinprawami monady bez konieczności definiowania ich joinod swaptyłu. Sprawdzę to i dam znać.
Petr
@Petr: W obecnym stanie zgadzam się z Rafaelem, że nie jest to do końca dowód, którego szukam, ale jestem również ciekawy, czy można go naprawić zgodnie z wytycznymi, o których wspomniałeś.
Brent Yorgey,
1
@ PetrPudlák Wow, bardzo ładnie! Tak, całkowicie to teraz kupuję. Oto kilka naprawdę interesujących spostrzeżeń. Nie przypuszczałbym, że sama możliwość skonstruowania zamiany może prowadzić do sprzeczności, bez odniesienia do żadnego z praw monad! Gdybym mógł zaakceptować wiele odpowiedzi, zaakceptowałbym również tę.
Brent Yorgey
4

Twoje łącze odnosi się do tego typu danych, więc spróbujmy wybrać konkretną implementację: data A3 a = A3 (A1 (A2 a))

Samowolnie wybiorę A1 = IO, A2 = []. Zrobimy też to newtypei nadamy mu szczególnie spiczastą nazwę, dla zabawy:

newtype ListT IO a = ListT (IO [a])

Wymyślmy dowolną akcję tego typu i uruchommy ją na dwa różne, ale równe sposoby:

λ> 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]

Jak widać, to łamie prawo skojarzeń: ∀x y z. (x >=> y) >=> z == x >=> (y >=> z).

Okazuje się, że ListT mjest monadą tylko wtedy, gdy mjest monadą przemienną . Uniemożliwia to komponowanie dużej kategorii monad [], co łamie uniwersalną zasadę, że „komponowanie dwóch dowolnych monad daje monadę”.

Zobacz też: https://stackoverflow.com/a/12617918/1769569

hpc
źródło
11
Myślę, że to tylko pokazuje, że jedna konkretna definicja ListTnie tworzy monady we wszystkich przypadkach, a nie pokazuje, że żadna możliwa definicja nie zadziała.
CA McCann
Nie muszę. Zaprzeczenie „za to wszystko, że” jest „istnieje kontrprzykład”. Zadane pytanie brzmiało: „dla wszystkich monad ich kompozycja tworzy monadę”. Pokazałem kombinację typów, które same w sobie są monadami, ale nie potrafią komponować.
hpc
11
@hpc, ale skład dwóch monad to coś więcej niż kompozycja ich typów. Potrzebujesz też operacji, a moja interpretacja pytania Brenta jest taka, że ​​może nie być metodycznego sposobu wyprowadzenia wykonania operacji - szuka czegoś jeszcze mocniejszego, że niektóre kompozycje nie mają operacji spełniających prawa, czy możliwe do uzyskania lub nie. Czy to ma sens?
luqui
Tak, Luqui ma rację. Przepraszam, jeśli moje pierwotne pytanie nie było jasne.
Brent Yorgey,
To, czego tak naprawdę brakuje w tej odpowiedzi, to Monadinstancja dla ListTi wykazanie, że nie ma innych. Stwierdzenie brzmi: „dla tego wszystkiego istnieje tamto”, a więc zaprzeczeniem jest „istnieje to, co dla tego wszystkiego”
Ben Millwood,