[Haskell-beginners] Red-black tree performance

[Adrien Haxaire]

On Tue, Mar 20, 2012 at 09:03:30PM +0000, Lorenzo Bolla wrote:
> On Tue, Mar 20, 2012 at 5:30 PM, Heinrich Apfelmus <
> apfelmus at quantentunnel.de> wrote:
> > Huh, why foldr' and not Data.List.foldl' ? As far as I understand, the
> > former has to evaluate the whole spine of the list first before it can
> > begin to assemble the tree. The latter can start building trees right away.
> >
> >
> Yes, definitely foldl' is worth a try, too:
>  main = putStrLn $ show $ maxTree $ foldl' (flip insert) Empty toInsert
> 
> L.

I tried with foldl'. I modified the code at several places to match the argument pattern, and now I see why flip is so useful :) The conclusion is also interesting: the productivity climbs up to 92%, while the calculation time raises to 6.3s. I guess that the choice is space or time, as often.

Another interesting point. By using foldr' and removing the exclamation marks in the Tree data type, I even get better results: 3.76s. Which means a ratio of 5.87. I tried adding some bang patterns and inline pragmas but it didn't help. 

I also ran the benchmark with 10 000 000 insertions and the ratio remains around 6. Which is quite acceptable, right? I'll be glad to show those results tomorrow.

I wouldn't imagine that GHC would optimize so well plain Haskell code. The algorithm is beautiful, its implementation too, and it produces fast code. Dear it's so great to learn Haskell!

Thank you Lorenzo and Heinrich, I have learnt a lot today. 

Best regards,
Adrien

-- 
Adrien Haxaire 
www.adrienhaxaire.org | @adrienhaxaire