DData revision /Bags

[Christian Maeder]

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