39 votes

Un exemple simple montrant que IO ne satisfait pas les lois de la monade?

J'ai vu mentionné qu' IO n'est pas satisfaire à la monade des lois, mais je n'ai pas trouvé un exemple simple montrant que. Quelqu'un sait-elle un exemple? Merci.

Edit: Comme ertes et n.m. a souligné, à l'aide de seq est un peu illégal, car il peut faire toute monade échouer les lois (combiné avec undefined). Depuis undefined peut être considéré comme un non-terminaison de calcul, il est parfaitement bien pour l'utiliser.

Donc, la version révisée de la question est: Quelqu'un sait un exemple montrant que l' IO ne parvient pas à satisfaire la monade lois, sans l'aide d' seq? (Ou peut-être une preuve qu' IO satisfait les lois s' seq n'est pas autorisé?)

42voto

ertes Points 319

Toutes les monades en Haskell ne sont que des monades si l'on exclut l'étrange seq combinator. Ceci est également vrai pour IO. Depuis seq n'est pas réellement une fonction régulière, mais implique la magie que vous avez à les exclure de la vérification de la monade des lois pour la même raison, vous devez exclure unsafePerformIO. À l'aide de seq vous pouvez prouver que toutes les monades de mal, comme suit.

Dans la catégorie de Kleisli la monade donne lieu à des return est l'identité morphism et (<=<) est la composition. Donc, return doit être une identité pour (<=<):

return <=< x = x

À l'aide de seq même de l'Identité et Peut-être ne pas être monades:

seq (return <=< undefined :: a -> Identity b) () = ()
seq (undefined            :: a -> Identity b) () = undefined

seq (return <=< undefined :: a -> Maybe b) () = ()
seq (undefined            :: a -> Maybe b) () = undefined

25voto

Daniel Fischer Points 114146

tl;dr avance: seq est le seul moyen.

Depuis la mise en œuvre de l' IO n'est pas prescrit par la norme, on peut seulement regarder les implémentations spécifiques. Si l'on regarde de GHC en œuvre, il est disponible à partir de la source (peut-être que certains de derrière-le-scènes traitement spécial de la IO introduit les violations de la monade des lois, mais je ne suis pas au courant d'un tel événement),

-- in GHC.Types (ghc-prim)
newtype IO a = IO (State# RealWorld -> (# State# RealWorld, a #))

-- in GHC.Base (base)
instance  Monad IO  where
    {-# INLINE return #-}
    {-# INLINE (>>)   #-}
    {-# INLINE (>>=)  #-}
    m >> k    = m >>= \ _ -> k
    return    = returnIO
    (>>=)     = bindIO
    fail s    = failIO s

returnIO :: a -> IO a
returnIO x = IO $ \ s -> (# s, x #)

bindIO :: IO a -> (a -> IO b) -> IO b
bindIO (IO m) k = IO $ \ s -> case m s of (# new_s, a #) -> unIO (k a) new_s

thenIO :: IO a -> IO b -> IO b
thenIO (IO m) k = IO $ \ s -> case m s of (# new_s, _ #) -> unIO k new_s

unIO :: IO a -> (State# RealWorld -> (# State# RealWorld, a #))
unIO (IO a) = a

il est implémenté comme un (stricte) de l'état monade. Ainsi, toute violation de la monade lois IO fait de, est également faite par Control.Monad.State[.Strict].

Regardons la monade lois et de voir ce qui se passe dans IO:

return x >>= f ≡ f x:
return x >>= f = IO $ \s -> case (\t -> (# t, x #)) s of
                              (# new_s, a #) -> unIO (f a) new_s
               = IO $ \s -> case (# s, x #) of
                              (# new_s, a #) -> unIO (f a) new_s
               = IO $ \s -> unIO (f x) s

Ignorant le newtype wrapper, qui signifie return x >>= f devient \s -> (f x) s. La seule façon de (peut-être) la distinction que d' f x est seq. (Et seq ne peut distinguer si l' f x ≡ undefined.)

m >>= return ≡ m:
(IO k) >>= return = IO $ \s -> case k s of
                                 (# new_s, a #) -> unIO (return a) new_s
                  = IO $ \s -> case k s of
                                 (# new_s, a #) -> (\t -> (# t, a #)) new_s
                  = IO $ \s -> case k s of
                                 (# new_s, a #) -> (# new_s, a #)
                  = IO $ \s -> k s

ignorant le newtype wrapper de nouveau, k est remplacé par \s -> k s, ce qui est encore seulement se distinguent par seq, et seulement si, k ≡ undefined.

m >>= (\x -> g x >>= h) ≡ (m >>= g) >>= h:
(IO k) >>= (\x -> g x >>= h) = IO $ \s -> case k s of
                                            (# new_s, a #) -> unIO ((\x -> g x >>= h) a) new_s
                             = IO $ \s -> case k s of
                                            (# new_s, a #) -> unIO (g a >>= h) new_s
                             = IO $ \s -> case k s of
                                            (# new_s, a #) -> (\t -> case unIO (g a) t of
                                                                       (# new_t, b #) -> unIO (h b) new_t) new_s
                             = IO $ \s -> case k s of
                                            (# new_s, a #) -> case unIO (g a) new_s of
                                                                (# new_t, b #) -> unIO (h b) new_t
((IO k) >>= g) >>= h = IO $ \s -> case (\t -> case k t of
                                                (# new_s, a #) -> unIO (g a) new_s) s of
                                    (# new_t, b #) -> unIO (h b) new_t
                     = IO $ \s -> case (case k s of
                                          (# new_s, a #) -> unIO (g a) new_s) of
                                    (# new_t, b #) -> unIO (h b) new_t

Maintenant, nous avons généralement

case (case e of                    case e of
        pat1 -> ex1) of       ≡      pat1 -> case ex1 of
  pat2 -> ex2                                  pat2 -> ex2

par l'équation 3.17.3 déplacements.(a) de la langue de rapport, de sorte que cette loi ne vaut pas seulement modulo seq.

En résumé, IO satisfait la monade lois, sauf pour le fait qu' seq peut distinguer undefined et \s -> undefined s. La même chose vaut pour State[T], Reader[T], (->) a, et toutes les autres monades l'enveloppant d'un type de fonction.

8voto

Chris Taylor Points 25079

L'un des monade lois, c'est que

m >>= return ≡ m

Nous allons essayer dans GHCi:

Prelude> seq ( undefined >>= return :: IO () ) "hello, world"
"hello, world"

Prelude> seq ( undefined :: IO () ) "hello, world"
*** Exception: Prelude.undefined

Donc, undefined >>= return n'est pas le même que undefineddonc IO n'est pas une monade. Si nous cherchons la même chose pour l' Maybe de l'errance, de l'autre main:

Prelude> seq ( undefined >>= return :: Maybe () ) "hello, world"
*** Exception: Prelude.undefined

Prelude> seq ( undefined :: Maybe () ) "hello, world"
*** Exception: Prelude.undefined    

Les deux expressions sont identiques - si Maybe n'est pas exclu d'être une monade par cet exemple.

Si quelqu'un a un exemple qui ne repose pas sur l'utilisation de l' seq ou undefined je serais intéressé de le voir.

3voto

comonad Points 1852
 m >>= return ≡ m
 

est cassé:

 sequence_ $ take 100000 $ iterate (>>=return) (return ()) :: IO ()
 

encombrer la mémoire et augmenter le temps de calcul, tandis que

 sequence_ $ take 100000 $ iterate (>>=return) (return ()) :: Maybe ()
 

ne fait pas.

AFAIR, il existe un transformateur Monad qui résout ce problème; si je me trompe, il s’agit du Transformateur Monad Codensity.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X