[Haskell-cafe] ANN: signed-multiset-0.1

Stefan Holdermans stefan at vectorfabrics.com
Wed Apr 25 11:39:29 CEST 2012

Wren, Sjoerd,

>>> This is not just about map, but it also a problem for the Monoid instance. You are basically adding an extra identity element, 0, to the max monoid, which works but is weird.

>> Still that's how union is typically defined for hybrid sets. It's what happens if want union and empty to behave as generalisations of these concepts for ordinary (multi)sets.

> Why? Whenever I've dealt with bags, the appropriate way to handle collision on union has been to use addition--- not maximization. Ditto for all the other set ops. Addition seems far more natural as the extension from basic sets. The fact that you have negative multiplicities only underscores the naturality of addition[1]. Why do you think max is natural?

The union of two sets is typically defined as the smallest set that is a superset of both the operands; this definition extends nicely for multisets and hybrid sets [1,2,3].

I do not recall claiming maximisation to be "natural"; what's natural for one application, may not be for another. The library provides both union (based on maximisation) and additive union, and furthermore gives Monoid instances over both of them. Not having a preference for either one of them, I thought that having both of them in the library made sense.

That said, my goal was never to upload a package that only leads to confusion and false expectations. As the common opinion seems to be that a maximising union is bad, I will drop it from the library and deprecate the package on Hackage.

Thanks for your feedback,


[1] Wayne D. Blizard: Multiset Theory. Notre Dame Journal of Formal Logic 30(1): 36-66 (1989)
[2] Wayne D. Blizard: Negative Membership. Notre Dame Journal of Formal Logic 31(3): 346-368 (1990)
[3] Apostolos Syropoulos: Mathematics of Multisets. WMP 2000: 347-358

More information about the Haskell-Cafe mailing list