Rename MultiSet to Bag, MultiDict => MultiMap?

[joshlemer]

Bag is a lot less verbose than MultiSet, and MultiDict is also pretty awkward to try and say aloud.

[julienrf]

The name MultiDict was chosen to not conflict with the existing MultiMap.

Is Bag an established name for sets containing possibly multiple occurrences of their elements?

[joshlemer]

Bag does appear to be an established name:

https://en.wikipedia.org/wiki/Set_(abstract_data_type)#Multiset
https://en.wikipedia.org/wiki/Multiset
https://commons.apache.org/proper/commons-collections/userguide.html#Bags

but you're likely right, that MultiSet is more commonly used, I'm not sure.

That's too bad about the MultiMap conflict.

[joshlemer]

This does raise the question of why we need a mutable.MultiMap in stdlib as well as a mutable.MultiDict in collections-contrib. Is there an end game of deprecating the stdlib version?

[julienrf]

I’m in favor of deprecating mutable.MultiMap but anyways we need to make both solutions cohabit together during the transition period.

[Ichoran]

Do we need both a counted set and a set which retains original copies? Although both can occasionally be useful, I would tend to say that most uses of the latter would just as well be served by a MultiMap. It's only the former that is really awkward and inefficient.

However, I don't think the counted set is very intuitively a Bag. That's not how physical bags work: you might not care that apples are different, but you get the same one out that you put in. So 👎 for MultiSet to Bag naming, assuming that MultiSet is a counted set. If it is not a counted set, 👎 for having it at all.

Also 👎 to introducing a name collision between the old MultiMap trait and a new MultiMap that may have both immutable and mutable variants. MultiDict is awkward, though. In principle, 👍 for finding something better. ManyMap or KeyBag perhaps. If KeyBag, then I guess MultiSet as a plain Bag is okay. Or maybe have all three: CountedBag, Bag, and KeyBag. But they will all be distinct APIs, I suspect, so maybe Bag is again bad.

[julienrf]

The MultiSet here is a counted multiset: https://github.com/scala/scala-collection-contrib/blob/master/src/main/scala/scala/collection/MultiSet.scala#L50-L53

I prefer MultiDict over KeyBag or ManyMap. https://www.google.com/search?q=multidict

[joshlemer]

Thanks @Ichoran ! Some points:

However, I don't think the counted set is very intuitively a Bag. That's not how physical bags work: you might not care that apples are different, but you get the same one out that you put in. So 👎 for MultiSet to Bag naming

So if I interpret correctly, you're saying that Bag is unintuitive, because when you insert an element into it, you expect that exact object (up to reference identity) should be found in the resulting Bag. This critique is fair enough in isolation but in Scala-land the ethos is generally that we don't care about reference equality and only care about value equality. For instance, you might have made the same critique of Sets -- that you expect that when you put an apple in a Set and get it back out, you get the same one you put in.

Now for some quick points for the name change:

• Bag has 3 letters vs MultiSet's 8, so it's much more convenient to type, which makes a pretty big difference when we treat collection apply as "literal" syntax (Bag(...)). The length savings is the same difference as Seq vs Sequence for instance. This may seem like a silly point, but anecdotally, I've even heard of people using Seq over List just to save one char.

• While MultiSet is one accepted term and possible the most popular, Bag is not too much less popular, and avoids potentially confusing people into thinking that a MultiSet is some kind of special case of Set (a la HashSet/TreeSet/etc), when in fact MultiSets/Bags have nothing to do with Sets in the Iterable hierarchy, and do not behave like Sets.

• I think that the Bag analogy very nicely visualizes what it is we're describing. A bag is an unordered collection of data, and a bag is equal to an other bag if and only if the two contain the same elements (including arity), ignoring order. The term Bag really drives home that order is ignored, IMO, because bags are all jumbled up/unstructured inside.

[Ichoran]

You can't get elements out of sets, and if you manage to, you do get one that you put in (if you put in duplicates, you obviously only get one of them out).

The bag is acting more like a bank: you deposit an item, and you get out an equivalent item, but not necessarily the one you put in. (Though it's weirder if counted--it will give you back the same item multiple times, rather than drawing separate instances from a vault of available instances.)

The point about the length of the name is a good one, though. That may be important enough to override all the other concerns.

[Ichoran]

Oh, also, next time my groceries end up packed all jumbled up/unstructured, I will remind myself that it is because they were put in a bag 😂

[julienrf]

I’m convinced that Bag is a good name for counted sets. But the problem is more on the side of MultiDict. I’m not sure that KeyBag makes sense here. A MultiDict (or MultiMap) associates a set of values to a key.

[joshlemer]

@julienrf I also don't think KeyBag is an improvement over MultiDict. MultiMap is probably best, save for the name collision. If I had to think of a different name, and I do prefer to go with practical/"blue collar" names over academic ones, I might consider something like OneToMany but I'm not sure that's necessarily any better than MultiDict (though it has exact same length). 🤷‍♂