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)! HTH Christian