Exemple concret montrant que les monades ne sont pas fermés en vertu de composition (avec la preuve)?

Question

Il est bien connu que les foncteurs applicatifs sont fermés en vertu de composition, mais les monades ne sont pas. Cependant, j'ai eu du mal à trouver un béton contre-exemple montrant que les monades ne sont pas toujours composer.

Cette réponse donne [String -> a] comme un exemple de non-monade. Après avoir joué un peu avec elle pour un peu, je crois que c'intuitivement, mais cette réponse juste dit "rejoindre ne peut pas être mis en œuvre", sans vraiment avoir à justifier de motifs. Je voudrais quelque chose de plus formel. Bien sûr, il ya beaucoup de fonctions de type [String -> [String -> a]] -> [String -> a]; on doit montrer qu'une telle fonction n'est pas nécessairement satisfaire la monade lois.

Un exemple (accompagné de la preuve) de le faire; je ne suis pas nécessairement à la recherche pour une preuve de l'exemple ci-dessus, en particulier.

Answer 1

Considérer cette monade, qui est isomorphe à l' (Bool ->) monade:

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

et de composer avec l' Maybe monade:

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

Je demande qu' Bad ne peut pas être une monade.

---

Partielle, la preuve:

Il n'y a qu'une façon de définir fmap satisfait fmap id = id:

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

Rappel de la monade lois:

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

Pour la définition de l' return x, nous avons deux choix: B Nothing ou B (Just (P x x)). Il est clair que pour avoir un espoir de revenir x de (1) et (2), nous ne pouvons pas jeter x, nous avons donc à choisir la deuxième option.

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

Que les feuilles join. Puisqu'il y a seulement quelques entrées possibles, nous pouvons faire un cas pour chacun:

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

Depuis la sortie est de type Bad a, les seules options sont B Nothing ou B (Just (P y1 y2)) où y1, y2 doivent être choisis à partir d' x1 ... x4.

Dans les cas (A) et (B), nous n'avons pas de valeurs de type a, donc nous sommes obligés de revenir B Nothing dans les deux cas.

Cas (E) est déterminé par le (1) et (2) monade lois:

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

Pour revenir B (Just (P y1 y2)) dans le cas (E), cela signifie que nous devons ramasser y1 soit à partir d' x1 ou x3, et y2 soit à partir d' x2 ou 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))

De même, il dit que nous devons chercher y1 soit à partir d' x1 ou x2, et y2 soit à partir d' x3 ou x4. En combinant les deux, nous déterminons que le côté droit de (E) B (Just (P x1 x4)).

Jusqu'à présent, c'est du tout bon, mais le problème survient lorsque vous essayez de remplir la droite, pour (C) et (D).

Il y a 5 possible à droite, pour chacun d'eux, et aucun des combinaisons de travail. Je n'ai pas un bel argument pour cela, mais j'ai un programme que de manière exhaustive teste toutes les combinaisons:

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

Answer 2

Pour une petite de béton de contre-exemple, considérons le terminal monade.

data Thud x = Thud

L' return et >>= simplement aller de l' Thud, et les lois tenir trivialement.

Maintenant, nous allons aussi avoir l'écrivain monade pour le type Bool (avec, disons, le xor-monoïde de la structure).

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

Er, messagerie unifiée, nous aurons besoin de la composition

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

Maintenant, essayez de définir...

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

Parametricity nous dit qu' ??? peut ne dépendent en aucune façon utile sur x, donc il doit être une constante. En conséquence, join . return est nécessairement une fonction constante également, d'où la loi

join . return = id

doit échouer pour quelles que soient les définitions de l' join et return nous choisir.

Answer 3

La construction du tiers exclu

(->) r est une monade pour chaque r et Either e est une monade pour chaque e. Nous allons définir leur composition ((->) r à l'intérieur, Either e à l'extérieur):

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

Je prétends que si Comp r e ont une monade pour chaque r et e , puis nous avons pu réaliser la loi de veux du milieu. Ce n'est pas possible dans intuitionniste de la logique qui sous-tend typesystems des langages fonctionnels (la loi du tiers exclu est équivalent à avoir le call/cc opérateur).

Supposons Comp est une monade. Ensuite, nous avons

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

et donc, nous pouvons définir

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

(C'est juste l' swap fonction du papier, de la Composition de monades que Brent mentionne, Sect. 4.3, seulement avec newtype (de)constructeurs ajouté. Notez que nous ne faisons pas attention à ce que les propriétés de il a, la seule chose importante est qu'il est définissable et total.)

Maintenant, nous allons définir

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

et se spécialisent swap r = b, e = b, a = False:

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

Conclusion: Même si (->) r et Either r sont des monades, leur composition Comp r r ne peut pas être.

Remarque: notez Que c'est également reflétée dans la façon dont ReaderT et EitherT sont définies. Les deux ReaderT r (Either e) et EitherT e (Reader r) sont isomorphe a' r -> Either e a! Il n'y a aucun moyen de savoir comment définir monade pour le dual Either e (r -> a).

---

Échapper IO actions

Il existe de nombreux exemples dans la même veine qui impliquent IO et qui conduisent à s'échapper IO en quelque sorte. Par exemple:

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)

Maintenant, nous allons avoir

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)

Ce qui va se passer lorsque ce programme est exécuté? Il y a deux possibilités:

1. "Première" ou "Deuxième" est imprimé après , nous lisons input à partir de la console, ce qui signifie que la séquence d'actions a été inversé et que les actions de foo sont échappés dans la pure f.

2. Ou swap (d'où l' join) jette l' IO d'action et pas de "Premier", ni de "Deuxième" est jamais imprimé. Mais cela signifie qu' join viole la loi

   join . return = id
   

   parce que si join jette l' IO d'action à l'écart, puis

   foo ≠ (join . return) foo
   

D'autres similaires IO + monade combinaisons de conduire à la construction de

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

Leur join implémentations doivent permettre l' e pour s'échapper de la IO ou qu'ils doivent les jeter et les remplacer par quelque chose d'autre, en violation de la loi.

Answer 4

Votre lien de référence à ce type de données, nous allons donc essayer d'aller cueillir quelques spécifiques de mise en œuvre: data A3 a = A3 (A1 (A2 a))

Je vais choisissez arbitrairement A1 = IO, A2 = []. Nous allons également faire un newtype et lui donner un plus particulièrement pointé nom, pour le fun:

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

Nous allons venir avec une action arbitraire dans le type, et l'exécuter dans deux différents mais égaux façons:

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

Comme vous pouvez le voir, cela brise l'associativité de la loi: ∀x y z. (x >=> y) >=> z == x >=> (y >=> z).

Il s'avère, ListT m n'est qu'une monade s' m est un commutative monade. Ceci empêche une grande catégorie de monades de composer avec des [], ce qui rompt la règle universelle de la "composition de deux arbitraire monades donne une monade".

Voir aussi: http://stackoverflow.com/a/12617918/1769569