Hey Jan, Your answers are fine. You're reasoning at a high-level which is okay, and if you want to get into the details, you'll have to inline the StateT abstraction and reason directly with the low-level code.
But what confuses me why we get different behavior here:
Lazy.evalState (head `fmap` mapM return (1:undefined)) 0 1 Lazy.evalStateT (head `fmap` mapM return (1:undefined)) 0 *** Exception: Prelude.undefined
Both expressions are identical save for one letter. But what's hidden is a third: head `fmap` mapM return (1:undefined) :: IO Int The gotcha is that expr no. 2, by virtue of operating in StateT over IO, must match the behavior of no. 3, because the monadic space contains all of IO. Put another way, no. 1 and 2 are so similar syntactically, you'd think their values must match. But no, the monadic semantics of s -> IO (a, s) are such that it's no. 3 that no. 2 must match with.
From this I conclude that the second monad is strict, whereas the first is not. Is that correct?
So we've seen that Lazy.StateT is strict /in the effects/. Which prompts the question, well, how is it lazier than Strict.StateT then, for which this five-year-old posting helps answer: http://marc.info/?l=haskell-cafe&m=123618429420650
Assuming that is correct, does this mean that every monad stacked on top of an IO monad becomes strict??
In the sense of strict in the effects, I believe so but I haven't checked all cases.
Here's another example that illustrates this point: http://pastebin.com/0fAFmufA
Why is (4) not computed in constant space, whereas (3) is?
For the same reason that the traversable functions sequence and mapM diverge on infinite lists when working in IO. Unless you take the lazy I/O way out.
Finally, what ultimately bothers me is the following: is it true that if my state monad is built on top of an IO monad I cannot lazily consume a result of a mapM computation?
An IO mapM on an infinite list results in an /infinitely IO-effectful/ monadic value. Which is why mapM return diverges, even when each of those infinity of effects is null. Like why sum [0,0..] doesn't terminate either. Watch what happens when you replace "mapM return" by the moral equivalent of "return". The triple combo of traversable + IO + infinite list is bound to fail. Without recourse to lazy I/O, that is. -- Kim-Ee