Hi all! Taylor Campbell found a bug in Data.Map but wasn&#39;t able to post to this mailing list so I&#39;m submitting this on his behalf.<div><br></div><div>----------------------------</div><div><br></div><div><div>Deletion in Data.Map does not always preserve the balance of a tree.</div>

<div>Deletion in Data.Set appears to preserve the balance in some cases</div><div>where Data.Map does not; I don&#39;t know whether Data.Set always leaves</div><div>the tree balanced.  I have attached two files to test the balance of</div>

<div>trees after a random sequence of insertions and a pathological</div><div>sequence of deletions (deleteMin -- although this is not pathological</div><div>for some applications such as priority queues).  TestMap.hs reliably</div>

<div>demonstrates for me that deleteMin readily yields an unbalanced tree,</div><div>if I supply a size of 10000 to test_map.  TestSet.hs does not.  The</div><div>salient difference between Data.Set and Data.Map, I believe, is the</div>

<div>choice of delta (w in Adams&#39; paper), which is 4 in Data.Set and 5 in</div><div>Data.Map.</div><div><br></div><div>Since Adams&#39; paper claims that when alpha (i.e. 1/ratio) is 1/2, w</div><div>must exceed about 4.646, this seems suspect.  But I haven&#39;t analyzed</div>

<div>the reasoning in Adams&#39; paper to find whether his conclusions are</div><div>wrong.  What I do know is that I can break trees when w is 5, but I</div><div>have not been able to break them when w is 4.  I also noticed a</div>

<div>comment in Set.hs saying that a value of 4 for w improved performance</div><div>on many operations.</div><div><br></div><div>I have also not been able to break trees if I change deletion to use</div><div>join rather than balance.  But that slows everything down a good deal</div>

<div>more, I believe, than simply changing w from 5 to 4.</div><div><br></div><div><br></div></div>