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

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