# Bug in Data.Map

Wed Aug 4 12:51:49 EDT 2010

```On August 4, 2010 05:33:15 Milan Straka wrote:
> I am able to proof that for delta >= 5 the construction fails.
> I also think I am able to proof that for delta = 4 the construction
> works.

I guess it depends on what value you are using for the ratio (1/alpha in Adams
paper), but if you are using the standard ratio = 2 (alpha = 1/2), then delta
= 4 (w = 4 in Adams paper) violates the

alpha >= (2w+1)/(w^2-1)

#3 single rotation constraint (page 27).

It is actually a simplification of the full constraint, however, which was

alpha >= (wn+w+n)/(n(w^2-1)).

The key is then to realize that this is only violated when n = 1 for alpha =
1/2 and w = 4, and that this cannot actually occur in his Fig 6. diagram.  It
would require a right-right tree with 1/2 items.  For n = 2 and above you are
okay, so it would seem at least single rotations are guaranteed to work.

Actually, I was surprised to hear about the w = 5 case as when I last
implemented this (for a different language) I went over all the math (due to
the comment in the Haskell code).  Despite not agreeing with all his double
rotation simplifications, I also got that alpha = 1/2 and w = 5 were okay.

I'll have to take a closer look when I get more time.

Cheers!  -Tyson
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part.