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

[wren ng thornton]

On 4/23/12 9:18 AM, Stefan Holdermans wrote:
> 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?


[1] With addition, {a:-2} `union` {a:3} == {a:1} and so "negation" is 
exactly that, and zero multiplicity is exactly the case of not being an 
element because zero is the identity for addition.

Whereas with maximization {a:-2} `union` {a:3} == {a:3} so "negation" 
doesn't actually mean negation. What you actually mean is that your 
multiplicities are linearly ordered but do not have a bottom element (as 
they would for bags or sets). This can be useful for when there's no 
sound conception of "zero", as when dealing with interval scale 
variables in statistics 
<http://en.wikipedia.org/wiki/Level_of_measurement>. And if you left it 
at that, this would be sensible, though I'm not sure I'd have much use 
for it in my own work.

However, then you're tacking on that even though there's no zero in your 
measurement scale, for some reason one particular level is considered 
special and is used to mean that an element is not in the set. 
Consequently, if I start with some set {a:x} and union it with {a:1} 
repeatedly, then I'll find that a is in the set more and more often 
(which is good) except potentially at some point where suddenly a is not 
in the set, but then it'll be in the set again on the next turn. This 
seems extremely unnatural to me. It can have practical utility in 
certain contexts (e.g., if used in conjunction with addition to form the 
log-Viterbi semiring), but I don't see any justification for it being a 
natural extension of sets and bags.

-- 
Live well,
~wren