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

[Sjoerd Visscher]

On Apr 25, 2012, at 11:39 AM, Stefan Holdermans wrote:

> 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].

[3] differs from [1] and [2] (and your implementation). [3] defines the union as h(u) = max(f(u), g(u)) where f, g and h are multiplicity functions. [4] does the same. But [2] says on page 352: "For binary union, take the maximum of nonzero multiplicities", and this is also what your implementation does. (Map.unionWith max does not do a max if the key is not in one of the maps, i.e. if one of the multiplicities is 0.)

> 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.


I think if your union would follow the definition with max as in [3] and [4] it is not confusing. But then empty would not be the identity of that union (that would be the signed multiset with multiplicity negative infinity for all elements), so it would still not be a good choice for the Monoid instance.

greetings,
Sjoerd

> [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
[4] A Cavalcanti: Theoretical Aspects of Computing