Additional semigroup/monoid instances for Map

[dbeacham]

I've often found the below a useful semigroup/monoid instance for maps where m1 <> m2 performs an upsert dependent on the semigroup instance of the value types. If a key exists in both m1 and m2 then the new value is a1 <> a2, otherwise if the key exists in only one of the maps then the new map takes the corresponding value.

This is useful in configuration like contexts with the Last a semigroup.

newtype OptionMap k a = OptionMap { getOptionMap :: M.Map k a }

instance (Ord k, Semigroup a) => Semigroup (OptionMap k a) where
  (<>) (OptionMap m1) (OptionMap m2) = OptionMap $ M.unionWith (<>) m1 m2

instance (Ord k, Semigroup a) => Monoid (OptionMap k a) where
  mappend = (<>)
  mempty = AppendMap mempty

As the implementation above shows, this can be easily recovered with M.unionWith but you then can't leverage code that works generically over Semigroup and Monoid.

[treeowl]

There's already a discussion going on the libraries list about what to do about the semigroup and monoid instances

On Feb 26, 2018 11:11 AM, "David Beacham" [email protected] wrote:

I've often found the below a useful semigroup/monoid instance for maps where m1 <> m2 performs an upsert dependent on the semigroup instance of the value types. If a key exists in both m1 and m2 then the new value is a1 <> a2, otherwise if the key exists in only one of the maps then the new map takes the corresponding value.

This is useful in configuration like contexts with the Last a semigroup.

newtype OptionMap k a = OptionMap { getOptionMap :: M.Map k a } instance (Ord k, Semigroup a) => Semigroup (OptionMap k a) where (<>) (OptionMap m1) (OptionMap m2) = OptionMap $ M.unionWith (<>) m1 m2 instance (Ord k, Semigroup a) => Monoid (OptionMap k a) where mappend = (<>) mempty = AppendMap mempty

As the implementation above shows, this can be easily recovered with M.unionWith but you then can't leverage code that works generically over Semigroup and Monoid.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/haskell/containers/issues/539, or mute the thread https://github.com/notifications/unsubscribe-auth/ABzi_XA4zGesK-tVMFH3Pmx_-PPGtKdUks5tYtekgaJpZM4STfrp .

[dbeacham]

Thanks for the heads up - I'll get myself back on the list and take a look.

Does it make sense to close this issue for now then?

[andrewthad]

The three-week discussion period of the mailing list post ends today. To summarize the discussion for posterity's sake:

• Most people were alright with removing the instance
• Some people preferred to never reintroduce an instance
• Some people wanted to introduce a Semigroup-lifting instance after a delay of 1-5 years
• Some people wanted to introduce a Semigroup-lifting instance immediately

[andrewthad]

Pinging @treeowl. Sorry to be a bother about this, but I really would love to see the existing instance get replaced. Have you arrived at a decision on this matter?

[andrewthad]

Pinging again. I would love to see the instance get replaced by the more general semigroup-lifting one.

[treeowl]

Sorry. This has proven a rather controversial decision. I still haven't figured out the Right Thing to do here. :-(. Could you put together a PR with all the various newtypes we likely want to modify the Semigroup and Monoid behaviors?

[andrewthad]

Sorry, I'm not totally clear of the meaning of the question at the end. Do you mean writing newtypes like:

newtype UnionMap k v = UnionMap (Map k v)
instance (Ord k, Semigroup v) => Semigroup (UnionMap k v) where ...

And leaving the existing instances as they are?

[sjakobi]

For reference, the monoidal-containers package contains version of Map, IntMap and HashMap with Semigroup instances based on the value instances.

[fumieval]

monoidal-containers exists and certainly a useful package, but it drags a lot of dependencies (lens, semialign, vector, unordered-containers). I think it's also beneficial to have a newtype wrapper in this package.

[isovector]

An easy fix for this is to give the internal map the "proper" semigroup-lifting instance, expose it in module like Data.Map.Semigroup, and then implement today's behavior using the First semigroup in Data.Map (+ maybe some coerces.) The benefit is that today's behavior can always be implemented in terms of the proper semigroup instance, but the opposite is not true.

[sjakobi]

@isovector, do I understand correctly that you suggest that containers should offer multiple Semigroup instances for the same e.g. Map type, but export them from different modules? No newtypes?

[3noch]

I understood the idea to mean: Move Data.Map to Data.Map.Semigroup and change the Semigroup instance to the one we prefer. Then in Data.Map export a newtype wrapper that uses First to get back the original semantics. Of course this means that we need to wrap every single function in Data.Map as well which is a pain. Maybe there's a trick with classes or even CPP that we could use.

One sticky point is things like Data.Map.Semigroup.insert. Should they <> on overlapping keys or replace?

[isovector]

I think it would be challenging to argue that insert could possibly be anything other than insert e m = singleton e <> m or insert e m = m <> singleton e.

[treeowl]

I think it would be challenging to argue that insert could possibly be anything other than insert e m = singleton e <> m or insert e m = m <> singleton e.

The obvious thing would probably be

insertL e m = singleton e <> m
insertR m e = m <> singleton e

[3noch]

Or we could just not have insert at all. :D

[sjakobi]

monoidal-containers exists and certainly a useful package, but it drags a lot of dependencies (lens, semialign, vector, unordered-containers). I think it's also beneficial to have a newtype wrapper in this package.

How about splitting monoidal-containers into a core package with very few dependencies and one or multiple additional packages that provide the functionality that the other dependencies are needed for? these recently got a similar treatment.

(CC @bgamari)

[3noch]

That's a great idea but I think it's slightly off topic. Why can't containers have sensible instances and slowly obviate the need for packages that we all mostly regret must exist?

[sjakobi]

That's a great idea but I think it's slightly off topic.

The discussion in this issue seems to be about multiple things:

• Adding newtypes whose Semigroup instances lift the values' instances

  This is covered by monoidal-containers. If the dependency footprint of that package is problematic, the package could be split.

• Changing the existing Semigroup instances to lift the values' instances.

Obviously, both things are ultimately about getting the desired instances.

Personally, I'm in favour of changing the existing instances and I expect that this change would get fairly broad community support. But the devil appears to be in the details of the "migration" from the current instances to the new ones.

It would be helpful if someone could compare some migration variants and point out their pros and cons. Any volunteers?

[Atry]

We can move the existing instance to a deprecated module as an orphan instance, and create the new instance in another module, also as an orphan instance. The user will see an instance not found error when upgrade, which can be solved by import one of the orphan instance.

[Atry]

In spite of the concern of breaking backward compatibility in implementation changes in Semigroup instance, at least we can add some functions like

sFromList = fromListWith (<>)
sUnion = unionWith (<>)

[sjakobi]

We can move the existing instance to a deprecated module as an orphan instance, and create the new instance in another module, also as an orphan instance. The user will see an instance not found error when upgrade, and can be solved by import one of the orphan instance.

I really like that idea, @Atry!

Once the deprecated module is removed, we can move the new instance into the main module.

In spite of the concern of breaking backward compatibility in implementation changes in Semigroup instance, at least we can add some functions like

sFromList = fromListWith (<>)
sUnion = unionWith (<>)

I think it would be better if we kept this issue about the instances.

[Atry]

We might also want to migrate GHC.Ext.IsList instances.

[mixphix]

Is there a timeframe on this?

[treeowl]

The hordes are clamoring. I will attempt to address this issue this weekend.