Why is (monad) elegance so costly?

[Simon Peyton-Jones]

| However, my experiments with a simplified lambda-calculus=20
| example shows that (with GHC 5.00) the state monad is=20
| dramatically less efficient than the simple identity monad:
|=20
|     4 TIMES SLOWER, and
|     7 TIMES MORE MEMORY!
|=20
| Is this normal?  Acceptable?  Am I doing something wrong?

I've just measured your program with GHC 5.02.  The speed=20
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)     =3D let ... in \env -> ...
	eval (Add u v) =3D 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 =3D let ... in ...
	eval (Add u v) env =3D let .. in ...

Why doesn't GHC do this?  Because doing so risks losing sharing.
It's possible that you may say

	let v =3D 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. =20

Anyway I hope this helps explain where the costs come from.
I'm interested in examples like this because it helps to know=20
what analyses would be useful.

Simon