Imprecision about the identity of keys (when Eq is not the smallest reflexive relation)

[andreasabel]

This issue is related to #290, #291, #52 (that one found by github Related Issues). There are situations where one would distinguish equal keys (in the sense of Eq) and identical keys (in the extreme pointer-identity).

The following is a (unrealistic) mock scenario, but it exemplifies the point. Here Eq on keys is very generous:

import Data.Map (Map)
import qualified Data.Map as Map

newtype Key = Key { theKey :: Integer }
  deriving (Show)

instance Eq Key where
  _ == _ = True

instance Ord Key where
  compare _ _ = EQ

test = show
     $ Map.update (const $ Just "bar") (Key 2)
     $ Map.singleton (Key 1) "foo"

What do we expect test to be? What does the documentation predict?
Lets read the documentation for Map.update!

containers/Data/Map/Internal.hs

Line 1062 in f7273d1

update :: Ord k => (a -> Maybe a) -> k -> Map k a -> Map k a

containers/Data/Map/Internal.hs

Lines 1053 to 1055 in f7273d1

	-- | /O(log n)/. The expression (@'update' f k map@) updates the value @x@
	-- at @k@ (if it is in the map). If (@f x@) is 'Nothing', the element is
	-- deleted. If it is (@'Just' y@), the key @k@ is bound to the new value @y@.

According to the documentation "... is (Just y), the key k is bound to the new value y", we expect the key k = Key 2 to be bound to "bar".
However, test is:

fromList [(Key {theKey = 1},"bar")]

This means the documentation is imprecise (wrong is a hard word). The precise wording would be "...the existing key (which is == k) is bound to the new value y".

On a more general note, the API for containers prevents the user to conveniently and efficiently inspect and update the keys of finite sets/maps. There seems to be a hidden assumption that no complex data structures are used as keys, and key equality is always uninteresting. This excludes practical scenarios where one would want to use finite maps also as managing data structure for the keys.

In case you wonder about practical scenario:
My own scenario is LALR parser generation where I maintain a map m from parse states (keys) to state numbers (values). A parse state is itself a map from parse items (dotted grammar rules) to lookaheads (token sets). LALR fuses parse states that only differ in the lookaheads, thus, for the sake of m I use an equality on parse states that ignores the lookaheads. (Eq is (==) ``on`` keysSet.) However, in the end I want the parse state with the largest lookaheads, thus, I need to update a key of m if I have a version of that key with larger lookaheads.

[jwaldmann]

Can you point to an example where properties of an API using Eq or Ord are specified even for the case that == (or <=) is not antisymmetric? It is usually avoided - with (implicit) reference to the Haskell standard saying "The Ord class is used for totally ordered datatypes." https://www.haskell.org/onlinereport/haskell2010/haskellch6.html#x13-1270006.3

But the someone will use such non-standard instances, and this will invariably lead to confusion, e.g., https://mail.haskell.org/pipermail/libraries/2018-December/029299.html (this is an instance of Hyrum's law http://www.hyrumslaw.com/ )

"update keys": in general, this would require re-balancing, while updating the value never does. Or do you want to restrict key updates to cases that don't re-balance (because the new key compares EQ to the old one)? How do you want to enforce this?

(Last I checked, implementation (Data.Map) only uses compare, never ==. But that's orthogonal to what you are saying.)

[sjakobi]

#316 seems related.