State monads don't respect the monad laws in Haskell
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 firstname.lastname@example.org 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
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?