search

haskell / containers

Assorted concrete container types
https://hackage.haskell.org/package/containers
315 stars 178 forks source link

mappend nor <> don't override #716

Open yaitskov opened 4 years ago

yaitskov commented 4 years ago

Hi,

I noticed inconsistency with Monoid and Semigroup implementations for List. Map implementations keep first value for duplicated key.

M.singleton 1 1  `mappend`  M.singleton 1 2
fromList [(1,1)]
λ M.singleton 1 1  <>  M.singleton 1 2
fromList [(1,1)]

but if map is constructed from combined equivalent lists then duplicated keys are overriden 

M.fromList $ M.toList (M.singleton 1 1)  <>  M.toList (M.singleton 1 2)
fromList [(1,2)]
treeowl commented 4 years ago

Yes, this has been noted before, and is weird. But people are probably relying on the current behavior, so we shouldn't change it. Would you like to open a PR to improve the documentation?

yaitskov commented 4 years ago

@treeowl , I will send the PR.

I have an idea how to tackle the merging ambiguity for a map. I noticed a submodule merging maps with a scary 6 argument function. Currently there is

instance (Ord k) => Semigroup (Map k v)

What if add Semigroup constraint to v? As for me it provides the most natural default way for combining values for duplicate keys. Plus a developer would have a control over merging with newtype wrapping with zero cost coercion, because v's role is representational. For migration purpose I would add an additional temporal protective class to prevent accidental merging.

instance (Ord k, Semigroup v, MapValueMerging v) => Semigroup (Map k v)

 (coerce ((coerce m1) :: Map Key (Keep Value) <> ((coerce m2) :: Map Key (Keep Value)))) :: Map Key Value
(coerce ((coerce m1) :: Map Key (Override Value) <> ((coerce m2) :: Map Key (Override Value)))) :: Map Key Value
yaitskov commented 4 years ago

The behavior for duplicated keys is already documented:

-- The 'Semigroup' operation for 'Map' is 'union', which prefers
-- values from the left operand. If @m1@ maps a key @k@ to a value
-- @a1@, and @m2@ maps the same key to a different value @a2@, then
-- their union @m1 <> m2@ maps @k@ to @a1@.
sjakobi commented 4 years ago

@yaitskov Changing the existing instances sounds rather hard to me. What do you think about https://github.com/haskell/containers/issues/539 though?