State monads don't respect the monad laws in Haskell

[John Launchbury]

Yes. Let me be clear.

It is not the fact that `seq` operates on functions that breaks foldr/build:
it is the fact that `seq` claims to be parametrically polymorphic when in
fact it is not. The parametricity result is weakened to the point that the
foldr/build proof no longer applies, and a counter example can be
constructed, viz.

  head = foldr const undefined
  one = build (\c n -> n `seq` c 1 n)

  result = head one

The one definition looks fine as the body to build is sufficiently
polymorphic, but that only because `seq` is lying.

John

>> I watched with interest the discussion about the ravages of `seq`.
>> 
>> In the old days, we protected uses of `seq` with a type class, to keep it at
>> bay. There was no function instance (so no problem with the state monads, or
>> lifting of functions in general), and the type class prevented interference
>> with foldr/build.
>> ...
> 
> Just a further remark: During discussion with Olaf about consequences of
> `seq` for foldr/build, respectively his type-inference based
> deforestation, I had the impression that there could very well be a
> function instance for `seq` not interfering with shortcut deforestation,
> provided this instance is restricted in the following way:
> 
> class Eval a where seq :: a -> b -> b
> 
> instance Eval d => Eval (c -> d)
> 
> I have no idea what would be a semantic justification for this instance
> declaration, except that it allows use of `seq` on at least some
> function types, but seems to outlaw all the critical cases where use of
> `seq` falsifies the foldr/build-rule.
> 
> 
> --
> Janis Voigtlaender