[Haskell-cafe] ANN: signed-multiset-0.1
wren ng thornton
wren at freegeek.org
Thu Apr 26 06:25:56 CEST 2012
On 4/25/12 7:27 PM, Stefan Holdermans wrote:
>>>>  defines the union as h(u) = max(f(u), g(u)) where f, g and h are multiplicity functions.
>>> Which is the same, as  is about multisets, not signed multisets.
>> Chapter 3 of  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).
More information about the Haskell-Cafe