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

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.

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

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.

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.

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

Monady nie komponują. Nie w sposób ogólny - nie ma ogólnego sposobu komponowania monad. Zobacz https://www.slideshare.net/pjschwarz/monads-do-not-compose