DData revision /Bags
maeder at tzi.de
Wed Mar 17 14:11:02 EST 2004
Ketil Malde wrote:
> My question is that since Set uses this equality, and MultiSet uses it
> with a count, I don't see how this leaves any space for Bag? Unless,
> that is, it uses an arbitrary equivalence relation, and bags an object
> in its quotient group (which possibly is a Set with "real" equality).
"Bag" and "MultiSet" are synonyms. Bags are something between Lists and
Sets. Lists become sets by changing "++" to "union" being commutative,
associative and idempotent, Lists become only Bags, when idempotency is
omitted. Thus the order of elements does not matter as for Sets, but for
Bags the multiplicity is important.
So either an implemtation as a "Map elem Int" (only positive natural
numbers) or as a sorted list (possibly with duplicates!) are possible.
Both implementations (the first one Daan called "MultiSet", the second
one "Bag") are equivalent, if the underlying equality for the elements
is strong. If the elements are only compared by an equivalence, then
obviusly the second implementation could also hold several different but
equivalent elements (what the Map cannot). However, putting different
but equivalent elements into a set would change the Bag property as also
strongly equal elements should contribute to a higher multiplicity.
> Maybe I'm mistaken, maybe there's some other way Bag makes sense --
> I've never really felt I needed Bag (nor MultiSet, although I've used
> explicit FMs with counts).
If you have a map with counts you may consider to use bags instead (and
trust in a stable and efficient implementation)!
More information about the Libraries