implementation of Map is not always left-biased for keys

[Flupp]

The documentation states, the implementation of Map is left-biased. I think, this property shall hold for values and keys. For example:

module Main where

import Data.Function (on)
import Data.Map.Lazy


main :: IO ()
main = do
  print
    $ insert    (OrdOnFst ('a', 'b')) ()
    $ singleton (OrdOnFst ('a', 'a')) ()
  print
    $ alter id  (OrdOnFst ('a', 'b'))
    $ singleton (OrdOnFst ('a', 'a')) ()


newtype OrdOnFst a b = OrdOnFst {unOrdOnFst :: (a, b)} deriving Show

instance Eq a => Eq (OrdOnFst a b) where
  (==) = (==) `on` (fst . unOrdOnFst)

instance Ord a => Ord (OrdOnFst a b) where
  compare = compare `on` (fst . unOrdOnFst)

actual output:

fromList [(OrdOnFst {unOrdOnFst = ('a','b')},())]
fromList [(OrdOnFst {unOrdOnFst = ('a','a')},())]

expected output:

fromList [(OrdOnFst {unOrdOnFst = ('a','b')},())]
fromList [(OrdOnFst {unOrdOnFst = ('a','b')},())]

In this example, insert works left-biased as expected, but alterdoes not. By looking at the source code of Data.Map.Base, I suspect there are other functions suffering from the same problem, e.g., update and updateWithKey.

[foxik]

I am not really sure what the right behaviour is and whether this change would be worth it.

If you are interested in this, the right place where to go is the libraries@haskell mailing list, see http://www.haskell.org/haskellwiki/Library_submissions#Guidance_for_proposers. Either just start only a discussion, or propose a change in the current behaviour (please include all Map/Set/IntMap/IntSet containers in the proposal if you make one).

[foxik]

Closing for now, please feel free to reopen if interested in it.