[containers] Proposal: Change to the Data.Map Monoid

Hi, Currently the Monoid instance for Data.Map is implemented using union/unions, which are left biased. On key collision, it discards values from the right hand side of `mappend` - https://github.com/ghc/packages-containers/blob/bae098fb0a3994bc2b0ec3313004... If you compare this with the Monoid for Maybe, it's like we're defaulting to First as the monoid instance for maps. A more useful instance, however very much a breaking change, would be to make the instance depend on a Monoid (or better yet, a Semigroup) for the values in the map: instance Monoid v => Monoid (Map k v) where mappend = unionWith mappend This lets us build up maps with values in a useful Monoid, and mappend them with gusto. Thoughts? - Nick Partridge Discussion period: 2 weeks.

This results in a silent change of semantics for all current users and _will_ break existing code _silently_. I am -1 on this change as there is no good way to manage the transition especially due to containers use as a boot package and the modicum of improvement strikes me as not worth the transition price. Moreover it is the "wrong" constraint. Maybe for instance is a terrible example to motivate this proposal as it adjoins a unit to a monoid pretending it is a semigroup to get a monoid. To union two maps we don't need a unit. Were Map/IntMap being defined from scratch? Reasonable. But given the very very large body of code that sits atop them that would break I have a hard time advocating for the ensuing debugging hell and silent breakages, Sent from my iPhone
On May 18, 2014, at 5:05 PM, Nick Partridge
wrote: Hi,
Currently the Monoid instance for Data.Map is implemented using union/unions, which are left biased. On key collision, it discards values from the right hand side of `mappend` - https://github.com/ghc/packages-containers/blob/bae098fb0a3994bc2b0ec3313004...
If you compare this with the Monoid for Maybe, it's like we're defaulting to First as the monoid instance for maps.
A more useful instance, however very much a breaking change, would be to make the instance depend on a Monoid (or better yet, a Semigroup) for the values in the map:
instance Monoid v => Monoid (Map k v) where mappend = unionWith mappend
This lets us build up maps with values in a useful Monoid, and mappend them with gusto.
Thoughts?
- Nick Partridge
Discussion period: 2 weeks. _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 On 19/05/14 04:19, Edward Kmett wrote: > This results in a silent change of semantics for all current users > and _will_ break existing code _silently_. - -1 on account of this. - -- Alexander alexander@plaimi.net https://secure.plaimi.net/~alexander -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.22 (GNU/Linux) Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iF4EAREIAAYFAlN5tXIACgkQRtClrXBQc7X2wgD+PJjrgTYDgg6V+ficg9PwSZFZ H+kkhsdT0ZUyZucBo7UA/0qvU+Na/5F0UMZLSMuYHzqWPPfurOPPPU2Avwx9JT1L =Hd8S -----END PGP SIGNATURE-----

Am 19.05.2014 02:05, schrieb Nick Partridge:
instance Monoid v => Monoid (Map k v) where mappend = unionWith mappend
This lets us build up maps with values in a useful Monoid, and mappend them with gusto.
This was discussed two years ago: http://www.haskell.org/pipermail/libraries/2012-April/017743.html That said, I'd also prefer your instance.

I think the Monoid instance for Data.Map should be *removed*. Reason: there are at least two meaningful instances. And, the documentation for the current instance is as out spoken as the fish in my non-existent aquarium: "" So, to use the Monoid instance, one has to consult the source code, just to see: instance (Ord k) => Monoid (Map k v) where mempty = empty mappend = union mconcat = unions Fantastic! I could never have though of these cunning implementations myself (sorry, sarcasm, I know). Why not trash these oneliners and free the Monoid instance for whatever the user wants it to do? Of course, I know, pragmatics, we cannot just remove functionality, might break existing code. But at least not silently. Maybe this could be sneaked in with another incompatible change of the Data.Map package? And after five years of having no Monoid instance, one could think of adding the most useful one. Or rather not, but have two newtypes with the respective meaningful implementations. Which we can also have here and now. On 19.05.2014 07:05, Henning Thielemann wrote:
Am 19.05.2014 02:05, schrieb Nick Partridge:
instance Monoid v => Monoid (Map k v) where mappend = unionWith mappend
This lets us build up maps with values in a useful Monoid, and mappend them with gusto.
This was discussed two years ago: http://www.haskell.org/pipermail/libraries/2012-April/017743.html
That said, I'd also prefer your instance.
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
-- Andreas Abel <>< Du bist der geliebte Mensch. Department of Computer Science and Engineering Chalmers and Gothenburg University, Sweden andreas.abel@gu.se http://www2.tcs.ifi.lmu.de/~abel/

Am 20.05.2014 20:49, schrieb Andreas Abel:
I think the Monoid instance for Data.Map should be *removed*.
I'd also like that.
Why not trash these oneliners and free the Monoid instance for whatever the user wants it to do?
Provided that the programmers know that they have to add a newtype and avoid orphan instances.

On May 20, 2014 11:49 AM, "Andreas Abel"
I think the Monoid instance for Data.Map should be *removed*.
+1 to removing the instance. I'm currently ambivalent towards adding newtypes over Map with Monoid instances. John L.
Reason: there are at least two meaningful instances.
And, the documentation for the current instance is as out spoken as the
fish in my non-existent aquarium:
""
So, to use the Monoid instance, one has to consult the source code, just
to see:
instance (Ord k) => Monoid (Map k v) where mempty = empty mappend = union mconcat = unions
Fantastic! I could never have though of these cunning implementations
myself (sorry, sarcasm, I know).
Why not trash these oneliners and free the Monoid instance for whatever
the user wants it to do?
Of course, I know, pragmatics, we cannot just remove functionality, might
break existing code.
But at least not silently.
Maybe this could be sneaked in with another incompatible change of the
Data.Map package? And after five years of having no Monoid instance, one could think of adding the most useful one. Or rather not, but have two newtypes with the respective meaningful implementations. Which we can also have here and now.
On 19.05.2014 07:05, Henning Thielemann wrote:
Am 19.05.2014 02:05, schrieb Nick Partridge:
instance Monoid v => Monoid (Map k v) where mappend = unionWith mappend
This lets us build up maps with values in a useful Monoid, and mappend them with gusto.
This was discussed two years ago: http://www.haskell.org/pipermail/libraries/2012-April/017743.html
That said, I'd also prefer your instance.
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
-- Andreas Abel <>< Du bist der geliebte Mensch.
Department of Computer Science and Engineering Chalmers and Gothenburg University, Sweden
andreas.abel@gu.se http://www2.tcs.ifi.lmu.de/~abel/
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

-1 to removing the instance. It breaks existing code for negligible benefit: you still have to add newtypes to pick the instance you want.

-----Original message----- From: Andreas Abel
Sent: 20 May 2014, 20:49 I think the Monoid instance for Data.Map should be *removed*. -----Original message----- From: Johan Tibell
Sent: 20 May 2014, 21:56 -1 to removing the instance. It breaks existing code for negligible benefit: you still have to add newtypes to pick the instance you want.
-1 from me as well. Although I agree that current instance is suboptimal, I do not believe the cost of removing it is justified. After all, the instance is not completely wrong, just not the one people usually expect. Cheers, Milan

-1 from me as well, though it is a much softer -1 than on the just breaking everyone silently by changing it.
_Lots_ of users initialize empty maps with mempty
Sent from my iPhone
On May 20, 2014, at 4:16 PM, Milan Straka
-----Original message----- From: Andreas Abel
Sent: 20 May 2014, 20:49 I think the Monoid instance for Data.Map should be *removed*. -----Original message----- From: Johan Tibell
Sent: 20 May 2014, 21:56 -1 to removing the instance. It breaks existing code for negligible benefit: you still have to add newtypes to pick the instance you want.
-1 from me as well.
Although I agree that current instance is suboptimal, I do not believe the cost of removing it is justified. After all, the instance is not completely wrong, just not the one people usually expect.
Cheers, Milan _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

-1 to removing the instance, it will just lead to incompatible packages when people declare their own instances to unbreak their code. John

Hi, Am Dienstag, den 20.05.2014, 17:47 -0400 schrieb Edward Kmett:
-1 from me as well, though it is a much softer -1 than on the just breaking everyone silently by changing it.
_Lots_ of users initialize empty maps with mempty
no problem, let’s replace it with instance (Ord k) => Monoid (Map k v) where mempty = empty mappend = error "do not use Monoid (Map k v), it is ambiguous" Greetings, Joachim PS: No, I’m not serious. -- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

On 21.05.2014 00:10, Joachim Breitner wrote:
Am Dienstag, den 20.05.2014, 17:47 -0400 schrieb Edward Kmett:
-1 from me as well, though it is a much softer -1 than on the just breaking everyone silently by changing it.
_Lots_ of users initialize empty maps with mempty
Well, this is another issue, empty should be overloaded via class Empty a where empty :: a but Edward does not like classes without laws.
no problem, let’s replace it with
instance (Ord k) => Monoid (Map k v) where mempty = empty mappend = error "do not use Monoid (Map k v), it is ambiguous"
That should be a compile-time error, please! ;-)
Greetings, Joachim
PS: No, I’m not serious.
-- Andreas Abel <>< Du bist der geliebte Mensch. Department of Computer Science and Engineering Chalmers and Gothenburg University, Sweden andreas.abel@gu.se http://www2.tcs.ifi.lmu.de/~abel/

On 2014-05-21 at 00:23:44 +0200, Andreas Abel wrote:
_Lots_ of users initialize empty maps with mempty
Well, this is another issue, empty should be overloaded via
class Empty a where empty :: a
Btw, isn't this what http://hackage.haskell.org/package/data-default provides?

I find myself rather hesitant to recommend that instantiation of the idea
ever since it exploded into a half-dozen packages full of orphan instances,
but yes.
-Edward
On Wed, May 21, 2014 at 6:38 AM, Herbert Valerio Riedel
On 2014-05-21 at 00:23:44 +0200, Andreas Abel wrote:
_Lots_ of users initialize empty maps with mempty
Well, this is another issue, empty should be overloaded via
class Empty a where empty :: a
Btw, isn't this what
http://hackage.haskell.org/package/data-default
provides? _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

At the risk of veering terribly off-topic... the splitting of data-default
into all of those packages caused me a bunch of dependency headaches, most
of which I still don't fully comprehend. I miss the good ol' days of a
single package.
On Wed, May 21, 2014 at 5:53 PM, Edward Kmett
I find myself rather hesitant to recommend that instantiation of the idea ever since it exploded into a half-dozen packages full of orphan instances, but yes.
-Edward
On Wed, May 21, 2014 at 6:38 AM, Herbert Valerio Riedel
wrote: On 2014-05-21 at 00:23:44 +0200, Andreas Abel wrote:
_Lots_ of users initialize empty maps with mempty
Well, this is another issue, empty should be overloaded via
class Empty a where empty :: a
Btw, isn't this what
http://hackage.haskell.org/package/data-default
provides? _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Sorry for continuing the off-topic, and for promoting a package of mine:
If you only need the class definition,
http://hackage.haskell.org/package/data-default-class is a better choice,
with no dependencies.
If you prefer a single package with all the dependencies (and with
additional generics support), my own fork might be useful:
http://hackage.haskell.org/package/data-default-generics
Although I mirrored the original package dependencies, many of which might
actually be unnecessary... (given the generics implementation).
Cheers
2014-05-21 15:59 GMT+01:00 Michael Snoyman
At the risk of veering terribly off-topic... the splitting of data-default into all of those packages caused me a bunch of dependency headaches, most of which I still don't fully comprehend. I miss the good ol' days of a single package.
On Wed, May 21, 2014 at 5:53 PM, Edward Kmett
wrote: I find myself rather hesitant to recommend that instantiation of the idea ever since it exploded into a half-dozen packages full of orphan instances, but yes.
-Edward
On Wed, May 21, 2014 at 6:38 AM, Herbert Valerio Riedel
wrote: On 2014-05-21 at 00:23:44 +0200, Andreas Abel wrote:
_Lots_ of users initialize empty maps with mempty
Well, this is another issue, empty should be overloaded via
class Empty a where empty :: a
Btw, isn't this what
http://hackage.haskell.org/package/data-default
provides? _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

There is always the option of folding Default into base, resolving concerns
about where you get instances for it and the ensuing package explosion once
and for all.
-Edward
On Wed, May 21, 2014 at 11:12 AM, João Cristóvão
Sorry for continuing the off-topic, and for promoting a package of mine:
If you only need the class definition, http://hackage.haskell.org/package/data-default-class is a better choice, with no dependencies.
If you prefer a single package with all the dependencies (and with additional generics support), my own fork might be useful: http://hackage.haskell.org/package/data-default-generics
Although I mirrored the original package dependencies, many of which might actually be unnecessary... (given the generics implementation).
Cheers
2014-05-21 15:59 GMT+01:00 Michael Snoyman
: At the risk of veering terribly off-topic... the splitting of data-default
into all of those packages caused me a bunch of dependency headaches, most of which I still don't fully comprehend. I miss the good ol' days of a single package.
On Wed, May 21, 2014 at 5:53 PM, Edward Kmett
wrote: I find myself rather hesitant to recommend that instantiation of the idea ever since it exploded into a half-dozen packages full of orphan instances, but yes.
-Edward
On Wed, May 21, 2014 at 6:38 AM, Herbert Valerio Riedel
wrote: On 2014-05-21 at 00:23:44 +0200, Andreas Abel wrote:
> _Lots_ of users initialize empty maps with mempty
Well, this is another issue, empty should be overloaded via
class Empty a where empty :: a
Btw, isn't this what
http://hackage.haskell.org/package/data-default
provides? _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

For what it's worth, I'd find Semigroup v => Monoid (Map k v) both
more useful and less surprising than the current unqualified monoid
instance for all maps. I say +1 if we can find a good way to deal
with the breakage. -0.1 otherwise - it's a significant concern.
On Wed, May 21, 2014 at 8:52 AM, Edward Kmett
There is always the option of folding Default into base, resolving concerns about where you get instances for it and the ensuing package explosion once and for all.
-Edward
On Wed, May 21, 2014 at 11:12 AM, João Cristóvão
wrote: Sorry for continuing the off-topic, and for promoting a package of mine:
If you only need the class definition, http://hackage.haskell.org/package/data-default-class is a better choice, with no dependencies.
If you prefer a single package with all the dependencies (and with additional generics support), my own fork might be useful: http://hackage.haskell.org/package/data-default-generics
Although I mirrored the original package dependencies, many of which might actually be unnecessary... (given the generics implementation).
Cheers
2014-05-21 15:59 GMT+01:00 Michael Snoyman
: At the risk of veering terribly off-topic... the splitting of data-default into all of those packages caused me a bunch of dependency headaches, most of which I still don't fully comprehend. I miss the good ol' days of a single package.
On Wed, May 21, 2014 at 5:53 PM, Edward Kmett
wrote: I find myself rather hesitant to recommend that instantiation of the idea ever since it exploded into a half-dozen packages full of orphan instances, but yes.
-Edward
On Wed, May 21, 2014 at 6:38 AM, Herbert Valerio Riedel
wrote: On 2014-05-21 at 00:23:44 +0200, Andreas Abel wrote:
>> _Lots_ of users initialize empty maps with mempty
Well, this is another issue, empty should be overloaded via
class Empty a where empty :: a
Btw, isn't this what
http://hackage.haskell.org/package/data-default
provides? _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Apologies for digging out an 18 month old post, but it shows some context.
In fact this proposal was made in 2012, resurrected in 2013, and re-made in 2014. Each time it has been defeated because it would break too much code to change it now.
Would there be any downside to providing a package with a newtyped Map with all operations ported over? The newtype already exists in semigroups as UnionWith (Map k) v; what is missing is the entire Map API.
Now that we have Data.Coerce (which we didn’t have at least the first time this was discussed) I believe I’m right in saying that you can basically patch the API over as:
module Data.MonoidMap.Strict where {
import qualified Data.Map.Strict as MS
import Data.Semigroup.Union
type Map k v = UnionWith (MS.Map k) v
— I don’t know if we need to use {-# INLINE #-} here or fully saturate singleton to get inlining to work
singleton :: k -> a -> Map k a
singleton = coerce MS.singleton
insert :: Ord k => k -> a -> Map k a -> Map k a
insert = coerce MS.insert
….
}
which is entirely mechanical (and can presumably be automated). Do the same for Lazy of course. And also for HashMap.
Add the correct Monoid instance (presumably using Semigroup since we have that as a dependency anyway). We can export also
fromMap :: Data.Map.Strict.Map k v -> Data.MonoidMap.Strict.Map k v
fromMap = coerce
and the reverse.
then legacy code is entirely unharmed, but new code which wishes to use the “correct” instance of Monoid has a package to import to use it, and it is relatively easy to co-exist with existing code using the old type, with an O(1) conversion function.
To be clear - this isn’t a library proposal, because it’s a proposal for a new package which will depend on containers and semigroups. However it is a suggestion of how we can solve the problem of Map having the wrong Monoid instance and not have to live with the problems forever. Who knows, one day in the future semigroups might be in base.
Jules
On 19 May 2014, at 01:05, Nick Partridge
Hi,
Currently the Monoid instance for Data.Map is implemented using union/unions, which are left biased. On key collision, it discards values from the right hand side of `mappend` - https://github.com/ghc/packages-containers/blob/bae098fb0a3994bc2b0ec3313004...
If you compare this with the Monoid for Maybe, it's like we're defaulting to First as the monoid instance for maps.
A more useful instance, however very much a breaking change, would be to make the instance depend on a Monoid (or better yet, a Semigroup) for the values in the map:
instance Monoid v => Monoid (Map k v) where mappend = unionWith mappend
This lets us build up maps with values in a useful Monoid, and mappend them with gusto.
Thoughts?
- Nick Partridge
Discussion period: 2 weeks. _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

On 9 Oct 2015, at 08:37, Julian Bean
Would there be any downside to providing a package with a newtyped Map with all operations ported over? The newtype already exists in semigroups as UnionWith (Map k) v; what is missing is the entire Map API.
Correction. The newtype exists in the package ‘reducers’ not ‘semigroups’.

On Fri, Oct 9, 2015 at 3:37 AM, Julian Bean
Apologies for digging out an 18 month old post, but it shows some context.
In fact this proposal was made in 2012, resurrected in 2013, and re-made in 2014. Each time it has been defeated because it would break too much code to change it now.
Would there be any downside to providing a package with a newtyped Map with all operations ported over? The newtype already exists in semigroups as UnionWith (Map k) v; what is missing is the entire Map API.
No downside at all. This is a package you could write and use today. To be clear - this isn’t a library proposal, because it’s a proposal for a
new package which will depend on containers and semigroups. However it is a suggestion of how we can solve the problem of Map having the wrong Monoid instance and not have to live with the problems forever. Who knows, one day in the future semigroups might be in base.
participants (15)
-
Alexander Berntsen
-
Andreas Abel
-
David Thomas
-
Edward Kmett
-
Henning Thielemann
-
Herbert Valerio Riedel
-
Joachim Breitner
-
Johan Tibell
-
John Lato
-
John Meacham
-
João Cristóvão
-
Julian Bean
-
Michael Snoyman
-
Milan Straka
-
Nick Partridge