[Haskell-cafe] Experiments with defunctionalization, church-encoding and CPS

[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

-- 
Eugene Kirpichov
Web IR developer, market.yandex.ru