| However, my experiments with a simplified lambda-calculus | example shows that (with GHC 5.00) the state monad is | dramatically less efficient than the simple identity monad: | | 4 TIMES SLOWER, and | 7 TIMES MORE MEMORY! | | Is this normal? Acceptable? Am I doing something wrong? I've just measured your program with GHC 5.02. The speed difference seems to be a factor of 2, not 4, though that is still not good. You can see what is going on if you give the flag -ddump-simpl to GHC, and then look for the function Main.eval. You'll see that eval has a shape like eval (Var x) = let ... in \env -> ... eval (Add u v) = let ... in \env -> ... This is bad, because eval is building a function closure for the \env, instead of taking its two arguments together as does simplEval. We'd prefer eval (Var x) env = let ... in ... eval (Add u v) env = let .. in ... Why doesn't GHC do this? Because doing so risks losing sharing. It's possible that you may say let v = eval term in do { v ; v ; v ; v } So you eval the term once, to get a state transformer, and then run that state transformer four times. If the 'env' arg is floated out, the work of the ".." in the above lets would be duplicated. Now *in this case* you aren't (ever) sharing a partial appliation of eval, and GHC could usefully spot this (but it doesn't at the moment). But if eval was exported, so GHC couldn't see all the applications of eval it could no longer do this trick. Maybe we could generate two versions. Another possibility would be to let the programmer give a pragma of some sort. Anyway I hope this helps explain where the costs come from. I'm interested in examples like this because it helps to know what analyses would be useful. Simon