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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
