Data.Map.mapKeys documentation differs from the actual behavior

[Adrian Hey]

Andriy Palamarchuk wrote:
> I'm currently improving documentation for Data.Map. mapKeys documentation says:
> 
> "The size of the result may be smaller if f maps two or more distinct keys to the same new key. In this case the value at the smallest of these keys is retained."
> 
> However the implementation retains the value of the *largest* key:
> 
> Prelude Data.Map> let map = fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]
> Prelude Data.Map> mapKeys (\ _ -> 1) map
> {1:="c"}
> Prelude Data.Map> mapKeys (\ _ -> 3) map
> {3:="c"}
> 
> See http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Map.html#v%3AmapKeys
> 
> Should I fix the documentation to confirm to the actual function behavior?

Yes, as a fix I would say change the documentation to be consistent with
the implementation, just in case somebody is actually using this
function in code that already "works". But I suspect that in reality
nobody is using it (except yourself possibly:-) as this function makes
no sense to me.

Personally, I think this function should be deprecated, which is what I
did in the AVL based Data.Map clone..

  http://darcs.haskell.org/packages/collections-ghc6.6/Data/Map/AVL.hs

Users should be made to specify the behaviour they want using
mapKeysWith (or use mapKeysOneToOne or mapKeysMonotonic). But now
that I look at it I see my (deprecated) "clone" of this function is
consistent with the originals documentation, but not it's
implementation. I guess I'd better fix that :-(

Regards
--
Adrian Hey