State monads don't respect the monad laws in Haskell

Simon Marlow
Tue, 14 May 2002 12:14:02 +0100

An interesting revelation just occurred to Simon P.J. and myself while
wondering about issues to do with exceptions in the IO monad (see
discussion on if you're interested).

The question we were considering was whether the following should hold
in the IO monad:

	(return () >>=3D \_ -> undefined) `seq` 42   =3D=3D  undefined

as we understand the IO monad it certainly shouldn't be the case.  But
according to the monad laws:

	(law)  return a >>=3D k  =3D=3D  k a
	so     (return () >>=3D \_ -> undefined) `seq` 42
      =3D>     ((\_ -> undefined) ()) `seq` 42
      =3D>     undefined `seq` 42
	=3D>     undefined

So the IO monad in Haskell, at least as we understand it, doesn't
satisfy the monad laws (or, depending on your point of view, seq breaks
the monad laws). =20

This discrepancy applies to any state monad.  Suppose we define

	return a =3D \s -> (s, a)
	m >>=3D k =3D \s -> case m s of (s', a) -> k a s'

	   return a >>=3D k
      =3D> \s -> case (return a) s of (s', a') -> k a' s'
	=3D> \s -> case (s, a) of (s', a') -> k a' s'
	=3D> \s -> k a s

	but (\s -> k a s) /=3D (k a) in Haskell, because seq can
	tell the difference.

What should the report say about this?