Bug in Data.Map

[Tyson Whitehead]

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.
Url : http://www.haskell.org/pipermail/libraries/attachments/20100804/70acc3ce/attachment.bin