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) VS 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 http://hpaste.org/fastcgi/hpaste.fcgi/view?id=10686 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? Regards, apfelmus -- http://apfelmus.nfshost.com