A paper about the balance of Data.Map and Set

Kazu Yamamoto ( 山本和彦 ) kazu at iij.ad.jp
Mon Oct 4 22:58:24 EDT 2010


This is call for reviewers of our paper.

We (Mr Hirai and I) have proved by Coq that the balance of Data.Map
with the parameters (3,2) can be maintained after insertion and
deletion. We are writing a paper about it and have already showed
Milan and Simon PJ. Simon suggested us to find those who are
interested in our paper on this ML. If someone are interested and
kindly volunteer to review it, please tell us. We will tell the URL of
our draft.

To be precise, we found the exact valid area of the parameters
(delta,ratio) not for Adams's scheme but for Nievergelt & Reingold's
scheme. The area is very complicated. (3,2) is one and only one
integer solution. Also we found ways to produce counter examples which
break balance after deletion.

Milan kindly did benchmark comparing Adams (4,2), Adams (3,2), and
Nievergelt & Reingold (3,2). Performance of insert, delete, lookup,
and merge is almost the same. Milan also pointed out that we should
prove that the join function can maintain balance. We are now workig
on this.



More information about the Libraries mailing list