One more possible fix of Data.Map

[Kazu Yamamoto ( 山本和彦 )]

Hello,

The comment of Data.Map says:

  Note: in contrast to Adam's paper, we use (<=) comparisons instead
  of (<) comparisons in [join], [merge] and [balance]. 
  Quickcheck (on [difference]) showed that this was necessary in order 
  to maintain the invariants. It is quite unsatisfactory that I haven't 
  been able to find out why this is actually the case! Fortunately, it 
  doesn't hurt to be a bit more conservative.

I tested Data.Map much and found:

- Test of [difference] does not stand for delta 5 with (>) instead of (>=)
- But stands for delta 4 with (>) instead of (>=)

To implement Adams's paper (in page 9) correctly, the "balance"
function should use (>) instead of (>=):

balance :: k -> a -> Map k a -> Map k a -> Map k a
balance k x l r
  | sizeL + sizeR <= 1    = Bin sizeX k x l r
  | sizeR > delta*sizeL   = rotateL k x l r  -- here
  | sizeL > delta*sizeR   = rotateR k x l r  -- and here
  | otherwise             = Bin sizeX k x l r
  where
    sizeL = size l
    sizeR = size r
    sizeX = sizeL + sizeR + 1

This is because Adams defines balanced as follows:
	size left <= w * size right
	size right <= w * size left

When balanced, rotation is not necessary.

I push my test environment to github:

	http://github.com/kazu-yamamoto/bst/

Here is usage:

	Please edit delta in Data/Map/Internal.hs.
	The balance function already use (>).
	% cd test
	% runghc -i.. TestMap.hs --maximum-generated-tests=10000 -t difference

P.S.

I think Milan said relating thing:
	http://article.gmane.org/gmane.comp.lang.haskell.libraries/13448

--Kazu