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

Eugene Kirpichov ekirpichov at gmail.com
Tue Oct 13 05:44:22 EDT 2009

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

The link points to code, a benchmark and 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

More information about the Haskell-Cafe mailing list