Not necessarily, a mapping describing an order suffice. Why not deliver an OrderedCollection as a possible subtype?
I think the problem is how to specify a Collection trait such that everyone thinks it is one. That's probably a hard task.
Maybe its something that is finite and iterable (probably non-deterministic).
But I think having List, Set and Map as trait aliases is useful and should be as general as possible, specializations of them should require creating other trait aliases referencing them.
Any need for a container trait is already highly specialized, and should be designed to suit the needs of the application that demands such a trait. (Any additional constraints will be unwelcome, and too lax of constraints make the trait unreliable.) Providing them in the standard library is only useful if there are applications that actually require the designs that std would offer. Which means describing such applications and their requirements. It doesn't make any sense to discuss abstractions in std if there's no measure of how useful they will be in terms of what problems they actually solve.
I think the problem is how to specify a Collection trait such that everyone thinks it is one.
The game here isn't just to produce a handful of random traits, dust your hands off and say "good enough. Hopefully that solves somebody's problems somewhere." Hand-waving and saying that you think they would be useful isn't productive. The problem is not "how do we get collection traits in std." It is "How do we show that collection traits are useful enough to justify being in std."
A lot of this discussion mirrors the number hierarchy traits as well, and like there, the requirements essentially depend upon the actual application the designers have in mind, and if people have different applications in mind they require different APIs.
Maybe the abstract base classes for collections in the Python standard library can also serve as some form of input. Admittedly, as a dynamic language, it is much more different to Rust than, say, Swift or Java.
At the same time, because these ABCs don't require inheritance (any class that has an __iter__() method is an Iterable, even if it doesn't inherit from it), they might map much closer to traits than classic inheritance hierarchies.
(I do agree that the best way forward is probably a concrete implementation of such traits and some examples of how they actually solve concrete problems.)
Since there were questions about there even is enough API surface to extract into common traits I was outlining what Java does, and only did for its top-level interface (note the "E.g."). I was not suggesting we should adopt the hierarchy 1:1. And even if we did, a type alias that sums a bunch of orthogonal traits into a convenience shorthand shouldn't be a big hurdle since you can always use the individual traits in a bound instead of the alias if you want to accept more restricted types that don't offer a full feature set.
How would ExactSize work with lazy and/or probabilistic collections such as Bloom filters or HyperLogLogs , that either produce elements on-demand or have only an approximate representation of their data?
My understanding is that those are not full-blown collections. They cannot produce elements. At best you can probabilistically probe for membership.
How would IntoParallelIterator work with collections that inherently can't be parallelized?
You can always feed a threadpool in batches taken sequentially from an iterator. It's not the most efficient way of driving a parallel iterator, but it's an option.