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' where sizeL = size l sizeR = size r sizeX = sizeL + sizeR The Data.Set code is identical except for the key. Cheers! -Tyson