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