[Haskell-cafe] strange stack overflow with Data.Map

[Christian Maeder]

Jean-Philippe Bernardy wrote:
>> insertWithKey f k x = insertWith (f k) k x
> 
> This is the case if the key type has structural equality. Otherwise,
> the key passed to the combining function, which comes from the map,
> can have a different value. Not that I support this style of coding,

I don't think, that we need to consider old and new keys (different but 
yielding EQ).

> It's a change to consider. We might want to deprecate the withKey
> variants (and implicitly the non-structural-equalilty types for keys).

At least {fold,map,filter,partition}WithKey functions are (I think) more 
useful than {insert,adjust,update}WithKey, so there will be no general 
rule for withKey-variants.

(I've never used {union,difference,intersection]WithKey, how important 
are these?)

I would not impose an implicit requirement for strong structural 
equality/order on the keys. But it would suffice to document which of 
two "equal" keys is dropped or kept. Maybe it is even possible to keep 
"Set a" somehow in sync with "Map a ()" or an identity "Map a a".
(And "Set (MapEntryPair a b)" to "Map a b")

On the other hand, if we would forget about biasing also for sets than 
insertion could be optimized to do nothing with sets that contain 
already the element. (Maybe that should even be changed so in Data.Set 
for efficiency reasons. An extra function might do the job of actually 
replacing an equal element.)

Christian

P.S. left-biasing for Set.intersection still needs to be checked in
(I've sent a patch some time ago)