Map for FGL

Adrian Hey ahey at
Wed Jan 11 02:09:26 EST 2006

On Monday 09 Jan 2006 6:28 pm, Adrian Hey wrote:
> That said, it should still do a pretty good job of balancing and the
> balancing mechanism itself and node size will have little impact on
> look up times (for example).

..or maybe not. Looking at this code again reminds me of something
strange that happened when I tested the RedBlack tree implementation
Chris Okasaki sent me a while back. It required precisely twice as
many comparisons as the RedBlack code Malcolm Wallace supplied.

I'm not sure exactly why, but I suspect it probably had something to
do with the use of either guarded equational style code (or maybe
if then elses) rather than "case compare x y of.." style code.

The FGL implementation seems to do the same thing. So I guess
lookup performance might not be too good either, at least for
non-trivial comparisons.

Adrian Hey


More information about the Libraries mailing list