[Haskell-cafe] Re: Experiments with defunctionalization,
church-encoding and CPS
apfelmus at quantentunnel.de
Sun Nov 1 07:12:10 EST 2009
Eugene Kirpichov wrote:
> 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
I'm not sure your example program is enough to justify the conclusions.
The main advantage of the Church-encoding of Maybe
type Maybe' a = forall b . b -> (a -> b) -> b
is that the latter has the pattern match for failure / success built-in
when used as a monad
m >>= g = \nothing just -> m nothing (\x -> g x nothing just)
m >>= g = case m of
Nothing -> Nothing
Just x -> g x
The algebraic data type has to check that the result was indeed Just x
whereas the Church-encoding can jump right to the success continuation.
The problem is that your tree doesn't really make use of this advantage.
For that, you need a completely left-biased tree, like for example
Fork 1 (Fork 2 (Fork 3 ... Leaf) Leaf) Leaf
testTree = fromList [1..100000]
fromList = foldr (\x t -> Fork x t Leaf) Leaf
I've implemented this and posted it below your version at
I've used the criterion benchmarking package, so you can run this
straight out of the box.
Even then, the results are mixed. The Church-encoding shines in GHCi as
it should, but loses its advantage when the code is being compiled. I
guess we have to look at the core if we want to know what exactly is
PS: I'm not entirely sure I'm using criterion correctly, in particular
concerning strictness. For instance, dropping the fromJust will
reduce the run-time of the "data Maybe" benchmark by 75%. Comments?
More information about the Haskell-Cafe