[Haskell-cafe] ANN: signed-multiset-0.1
wren ng thornton
wren at freegeek.org
Wed Apr 25 04:32:29 CEST 2012
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
More information about the Haskell-Cafe
mailing list