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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe