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

[wren ng thornton]

On 4/25/12 7:27 PM, Stefan Holdermans wrote:
> Sjoerd,
>
>>>> [3] defines the union as h(u) = max(f(u), g(u)) where f, g and h are multiplicity functions.
>>>
>>> Which is the same, as [3] is about multisets, not signed multisets.
>>
>> Chapter 3 of [3] is about Hybrid Sets.
>
> And there the union is defined by taking the *minimum* of multiplicities, which is even more strange.

FWIW, I've run into the minimum version of bags/multisets as well. It's 
a bit strange notionally, but mathematically it actually works out 
pretty well as I recall.


Do note that if we consider multisets to be sets with extra structure, 
then some minimisation is implicit in the maximization definition as 
well. That is, consider the definition in Syropoulos where a ("real") 
multiset is a tuple (X,p) of X a set and p an equivalence relation on X.

Given two multisets (X,p) and (Y,q), let (Z,r) be their max-union. Since 
we're thinking of these as sets with extra structure, we'd like for Z to 
be the union of X and Y. In order for multiplicities to work out right, 
that means we must require that X and Y be "maximally non-disjoint". 
That is, consider (W,r') where W is the intersection of X and Y, and r' 
is the restriction of r to W. We want that the multiplicities in (W,r') 
are the *minimum* of the multiplicities in (X,p) and (Y,q). That 
guarantees that elements are shared whenever possible, and hence that Z 
= X `union` Y is as small as possible while being consistent with the 
multiplicities on (X,p) and (Y,q).

-- 
Live well,
~wren