A simple example showing that IO doesn't satisfy the monad laws?

Question

I've seen mentioned that IO doesn't satisfy the monad laws, but I didn't find a simple example showing that. Anybody knows an example? Thanks.

Edit: As ertes and n.m. pointed out, using seq is a bit illegal as it can make any monad fail the laws (combined with undefined). Since undefined may be viewed as a non-terminating computation, it's perfectly fine to use it.

So the revised question is: Anybody knows an example showing that IO fails to satisfy the monad laws, without using seq? (Or perhaps a proof that IO does satisfy the laws if seq is not allowed?)

Answer 1

All monads in Haskell are only monads if you exclude the weird seq combinator. This is also true for IO. Since seq is not actually a regular function but involves magic, you have to exclude it from checking the monad laws for the same reason you have to exclude unsafePerformIO. Using seq you can prove all monads wrong, as follows.

In the Kleisli category the monad gives rise to, return is the identity morphism and (<=<) is composition. So return must be an identity for (<=<):

return <=< x = x

Using seq even Identity and Maybe fail to be monads:

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

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

Answer 2

tl;dr upfront: seq is the only way.

Since the implementation of IO is not prescribed by the standard, we can only look at specific implementations. If we look at GHC's implementation, as it is available from the source (it might be that some of the behind-the-scenes special treatment of IO introduces violations of the monad laws, but I'm not aware of any such occurrence),

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

it's implemented as a (strict) state monad. So any violation of the monad laws IO makes, is also made by Control.Monad.State[.Strict].

Let's look at the monad laws and see what happens in 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

Ignoring the newtype wrapper, that means return x >>= f becomes \s -> (f x) s. The only way to (possibly) distinguish that from f x is seq. (And seq can only distinguish it if 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

ignoring the newtype wrapper again, k is replaced by \s -> k s, which again is only distinguishable by seq, and only if 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

Now, we generally have

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

per equation 3.17.3.(a) of the language report, so this law holds not only modulo seq.

Summarising, IO satisfies the monad laws, except for the fact that seq can distinguish undefined and \s -> undefined s. The same holds for State[T], Reader[T], (->) a, and any other monads wrapping a function type.

Answer 3

One of the monad laws is that

m >>= return ≡ m

Let's try it out in GHCi:

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

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

So undefined >>= return is not the same as undefined, therefore IO is not a monad. If we try the same thing for the Maybe monad, on the other hand:

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

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

The two expressions are identical - so Maybe is not ruled out of being a monad by this example.

If anyone has an example that doesn't rely on the use of seq or undefined I would be interested to see it.

Answer 4

m >>= return ≡ m

is broken:

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

clutters memory and increases computation time, while

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

does not.

AFAIR there is a Monad Transformer which solves this problem; if I guess right, it is the Codensity Monad Transformer.