Unbiased Semigroup instance for Data.Map.Map

[kl0tl]

The Semigroup instance for Data.Map.Map is right-biased, meaning that duplicates are droped from the LHS, but the instance for Foreign.Object.Object requires a Semigroup constraint on its elements type to append duplicates!

We should at least document the difference or either bias the instance for Foreign.Object.Object or unbias the instance for Data.Map.Map.

I believe the behaviour of Foreign.Object.Object to be the most sensible here and would like the Data.Map.Map instance to be unbiased, especially now that we have Coercible.

The following would benefit from type applications, deriving via, constraint kinds and quantified constraints (:upside_down_face:) but is otherwise usable today and allows us to recover the behaviour of the current Semigroup instance for Data.Map.Map with _LeftBiased and the combinators from Data.Newtype (ala _LeftBiased foldMap and under2 _LeftBiased (<>) for example) given an unbiased instance:

data Bias

foreign import data Left :: Bias
foreign import data Right :: Bias

newtype Biased :: forall k. Bias -> (k -> Type) -> k -> Type
newtype Biased bias f a = Biased (f a)

_LeftBiased :: forall f a. f a -> Biased Left f a
_LeftBiased = Biased

_RightBiased :: forall f a. f a -> Biased Right f a
_RightBiased = Biased

derive instance newtypeBiased :: Newtype (Biased bias f a) _

instance semigroupLeftBiased :: (Semigroup (f (First a)), Coercible (f a) (f (First a))) => Semigroup (Biased Left f a) where
  append = coerce ((<>) :: f (First a) -> f (First a) -> f (First a))
instance monoidLeftBiased :: (Monoid (f (First a)), Coercible (f a) (f (First a))) => Monoid (Biased Left f a) where
  mempty = coerce (mempty :: f (First a))

instance semigroupRightBiased :: (Semigroup (f (Last a)), Coercible (f a) (f (Last a))) => Semigroup (Biased Right f a) where
  append = coerce ((<>) :: (f (Last a) -> f (Last a) -> f (Last a)))
instance monoidRightBiased :: (Monoid (f (Last a)), Coercible (f a) (f (Last a))) => Monoid (Biased Right f a) where
 mempty = coerce (mempty :: f (Last a))

[hdgarrood]

I would be on board without reservation if this were 3 or 4 years ago, but changing the Semigroup instance in this way could very easily break existing code in a way which is only surfaced at runtime. I think we would need to seek community input before doing this. See also #2, which discusses the Semigroup instance (although suggests a different one again).

[kl0tl]

Oh right, I thought it would be safe to strenghten the Semigroup instance context by requiring a Semigroup instance for the values but it would be unacceptable for singleton k [a] <> singleton k [b] to silently change meaning.

We could deprecate this instance and suggest another for Biased Left (Unbiased k) a with a Warn superclass (given an unbiased newtype over maps) in v0.14.x, then turn the warning into an error with a Fail superclass instead in v0.15.0 to ensure no one uses the instance anymore, then unbias it and deprecate the instance for Biased Left (Unbiased k) a in v0.16.x and finally remove it in v0.17.0. That’s perhaps too much churn though 😅

I guess we should rather add an unbiased newtype over maps and document the behaviour of the Semigroup instances for foreign objects and maps like it is done for hash maps then.

[hdgarrood]

I mean, I'm not saying let's not do it at all. I think it may be worth asking; the fact that Foreign.Object and Map differ in this way is definitely odd and a potential footgun, and I think this instance is arguably more useful; I've definitely wanted this behaviour in a few places before. I just think that approaching the community about it before we do it is probably necessary.

[garyb]

I'd almost argue that there shouldn't be a default instance, as like in the Additive and Multiplicative situation, both styles of instance are useful and it's not entirely clear to me that one should be blessed over the other as the default* - I've wanted both in roughly equal amounts, and now prefer to explicitly unionWith, as especially with the Object instance being different, it makes it clearer what is going to happen.

* Actually, as I was writing this, it occurred to me that if we follow the logic of our Maybe instance, then the Object-style instance should be the default, as it's essentially the same behaviour there raised to multiple values - we "fixed" this instance compared with the Haskell one, which originally did something like left-catch, (but was also changed to use a semigroup on the value later on). I guess, depending on the other discussion, the current behaviour should be the Alt instance for Map?

[hdgarrood]

The argument of following the logic of our Maybe instance is persuasive to me, yeah. Just to check we're on the same page: that line of thinking would suggest that we have alt be union, and append be unionWith append?

[garyb]

Yep, that's exactly what I had in mind 👍.

Unfortunately this still might be a sneakily breaking change? Perhaps even more so that swapping the append order, since if we change the instance and it just so happens that the Semigroup constraint remains satisfied, this can wildly change the behaviour of appending two maps.

[hdgarrood]

Yeah, it's definitely a sneakily breaking change, which is why I think we'd need to approach the community: firstly so that people are more likely to be aware, and secondly so that they have an opportunity to object.

[kl0tl]

I‘ve proposed in #36 (comment) a strategy to mitigate the risks of this change, at the cost of some churn. We can’t prevent the same program to behave differently when compiled with different versions of the compiler but at least we can guarantee that programs compiling without warnings at v0.x.y still compile without change of behaviour at version v0.(x+1).0

[hdgarrood]

We can present that as an option when we suggest this to the community, but honestly I'd prefer to just do it in one go.

[hdgarrood]

we can guarantee that programs compiling without warnings at v0.x.y still compile without change of behaviour at version v0.(x+1).0

We generally try to avoid cases where programs which continue to compile after a breaking compiler change but behave differently, but I don't think it's something we can guarantee. We do occasionally need to make changes which will cause behaviour changes, e.g. the change to fix sharing in function composition inlining in https://github.com/purescript/purescript/releases/tag/v0.13.0.

[kl0tl]

Oh ok, I thought leaving enough time to the ecosystem to adapt and guiding the transition with warnings and errors would make this pill easier to swallow (especially since that change wouldn’t fix any compiler bug). I’ll prepare a post to ask the community!

[paf31]

Please also consider that some people don't update their code with every release. Someone who jumps multiple major versions at once could miss the deprecation release, and have the same experience as if there hadn't been one at all.

[JordanMartinez]

This is another breaking change release that should be made in v0.15.0.

Per the Discourse post discussing this issue:

In v0.15.0, I believe we would deprecate the SemigroupMap newtype and add the unbiased Semigroup and Monoid instance back to Data.Map with a Warn that says something like “Instance differs from the instance defined in PS releases <= 0.13.x.” In v0.16.0, we would remove the SemigroupMap newtype and remove the Warn constraint on the Semigroup instance.

I don't think we should do what was originally described exactly. If we have a Warn on both the SemigroupMap and Map instances, then everyone will get compiler warnings for the rest of v0.15.0. In v0.15.0, I'd rather not having to see a new MonadZero-like warning for the rest of the release. I would rather we put a Warn on Map so that those who jump two breaking changes are still notified, and NOT put a Warn on SemigroupMap's instances.

In other words:

• v0.14.0
  • remove Map's Semigroup and Monoid instance
  • add SemigroupMap with unbiased Semigroup and Monoid instance
• v0.15.0
  • add unbiased Semigroup and Monoid instances back to Map with a Warn in case people jump two breaking changes
  • SemigroupMap's instances are untouched.
• v0.16.0
  • remove Warn on Map's Semigroup and Monoid instances.
  • add Warn on SemigroupMap's Semigroup and Monoid instances.
  • add deprecation notice to SemigroupMap
• v0.17.0
  • remove SemigroupMap

[JordanMartinez]

I've opened issues tracking the future breaking changes to make regarding this issue. Closing.