Bug in the proof of Data.FiniteMap and DData.Map

JP Bernardy jyp_7 at yahoo.com
Mon Mar 22 05:41:52 EST 2004

--- Robert Will <robertw at stud.tu-ilmenau.de> wrote:
> hi,
> both of the data structures are based on Adams'
> balancing algorithm
> which contains a bug -- at least in its proof. 
> (Perhaps it is
> correct, but I don't know anyone that knows if.)

Can you derive a counter-example from the
demonstration bug?

The current algorithm looks good enough for me, and I
am reluctant to change the implementation. I'd let
Daan choose the course of action with this respect.

As a side note, I've re-implemented the "SpellCheck"
test with DData, and it behaves ok. Besides, using
"Set" instead of "Map" improves performance by 10% or


Do you Yahoo!?
Yahoo! Finance Tax Center - File online. File on time.

More information about the Libraries mailing list