One more possible fix of Data.Map
Kazu Yamamoto ( 山本和彦 )
kazu at iij.ad.jp
Thu Aug 19 02:53:36 EDT 2010
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
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:
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
I think Milan said relating thing:
More information about the Libraries