Minor inefficiency in Data.Map and Data.Set?

Tyson Whitehead twhitehead at gmail.com
Mon Dec 21 00:38:25 EST 2009

I was looking at the Data.Map and Data.Set implementations and I think there 
is a slight inefficiency.  Consider the Data.Map code

  [glue l r]: glues two trees together.
  Assumes that [l] and [r] are already balanced with respect to each other.
glue :: Map k a -> Map k a -> Map k a
glue Tip r = r
glue l Tip = l
glue l r   
  | size l > size r = let ((km,m),l') = deleteFindMax l in balance km m l' r
  | otherwise       = let ((km,m),r') = deleteFindMin r in balance km m l r'

The call to balance should not be needed as subtracting one item from the non-
smaller of them cannot thrown them out of balance given they are already in 
balance with one another.  The only way they could be made out of balance 
would be to subtract an item for smaller one.  The replacement code is

glue l r   
  | sizeL > sizeR = let ((km,m),l') = deleteFindMax l in Bin sizeX km m l' r
  | otherwise     = let ((km,m),r') = deleteFindMin r in Bin sizeX km m l r'
    sizeL = size l
    sizeR = size r
    sizeX = sizeL + sizeR

The Data.Set code is identical except for the key.

Cheers!  -Tyson

More information about the Libraries mailing list