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

Heinrich Apfelmus 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
> 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

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
going on.

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 mailing list