On Tue, Oct 13, 2009 at 4:44 AM, Eugene Kirpichov
I took a toy problem - find the first node satisfying a predicate in a binary tree, started with a naive Maybe-based implementation - and experimented with 3 ways of changing the program: - Church-encode the Maybe - Convert the program into CPS - Defunctionalize the Church-encoded or CPS-transformed program http://hpaste.org/fastcgi/hpaste.fcgi/view?id=10686
The link points to code, a benchmark and conclusion.
Conclusion: - Haskell implements Maybe well enough that it is not possible to do better - Defunctionalization and consequent optimization yields same performance as the one with Maybe - Non-simplified CPS and Church-encoded representations do bad
You may find this collection of related papers interesting if you have not already seen them: http://lambda-the-ultimate.org/node/2423#comment-38384