Libcollections traits: a standard interface for all collections

[nightpool]

Mainly? It seemed like a good way to test out the feature. Wiki posts are editable by any logged in user (above trust level 0?) We can throw revisions back and forth too.

[cmr]

Ok, it’s worth trying!

[netvl]

Java collections library is not an example of design worth copying. It is weird and inconsistent; that Map is not a Collection was already mentioned, and that’s only one of its problems. It also does not distinguish between mutable and immutable collections.

I think that Scala collection library is much better; it has clean structure and separation between different kinds of collections. Even if exact hierarchy may be not feasible for Rust to have, it is a nice source of ideas.

[nightpool]

##Brainstorming:

Collections for libcollections

• HashSet, HashMap
• TreeSet, TreeMap
• BitSet
• EnumSet (is this just a BitSet on the inside?)
• Vector
• Ring Buffer
• BinaryHeap, PairingHeap
• some kind of Stack? there’s nothing like this in libcollections right now.
• Fixed size arrays, which are a language item

This is just a random grab bag of things out of the current libcollections, and the Java and Scala libraries. Feel free to add things!

[Gankro]

It would make more sense for every Collection to support a larger amount of methods, with the expectation that not all of these methods would be appropriate for every collection implementer, but methods that would be possible for every collection to support.

You’re probably right, it was a gut reaction I had late at night. However I don’t think it needs to be coupled to the entirely unobjectionable len and clear operations, that can be sanely and efficiently implemented by just about anything. Should we maybe break up the standard collection interface into lots of tiny bits, and then have some super-nice aggregate Collection trait in the same vein as Num? It’s sort of the exact opposite of the Java architecture. Instead of every structure being a collection, only the most robust structures are collections. One can then be viewed as a Stack, Collection, or Stack + Collection.

This goes back to my uncertainty on how granular we want the traits to be.

[Gankro]

Do we want both a DList (appropriate for a Deque), and SList (appropriate for a Queue or Stack)?

I would also nominate PriorityQueue to be renamed as BinaryHeap so PriorityQueue can be the trait it implements.

[nham]

I’m thinking you’re right. Java takes a very set-like view of what a collection is, and I definitely don’t think it’s productive to discuss whether a Map philosophically is or is not a collection. Scala’s collections library seems to be an excellent place to start. Even better would be to survey various collection libraries, making a list of all the structures we might want in libcollections, and then trying to organize them with traits. Are you aware of any other good examples to look at? Boost and the C++ standard library seem to be worth looking at. Also, Google’s Guava library for Java.

[netvl]

No, I’m a Java/Scala programmer, so I’m not well aware about libraries in other languages. Apart from these I worked with C/C++ (a long time ago and not for long), Delphi (even earlier than with C), Go, Haskell, D, JS and now Rust, and unfortunately I hadn’t seen more convenient and well-thought collections library than the one in Scala.

Guava is not really a collections library; sure, it does contain some very useful implementations of standard Java collection interfaces (I used them all the time in Java projects), and it adds a couple of new interfaces, e.g. multimap/multiset, bi-map, table, but still it is just an extension of standard Java collections library.

[nightpool]

Feel free to add things to my post everyone! Its a wiki, so every logged in user should be able to edit it. We’ll use that one as a baseline for implementations, then we’ll brainstorm traits, ok?

Guava is not really a collections library; sure, it does contain some very useful implementations of standard Java collection interfaces (I used them all the time in Java projects), and it adds a couple of new interfaces, e.g. multimap/multiset, bi-map, table, but still it is just an extension of standard Java collections library.

Add some of those to the wiki post, ok? I took a survey from my memory of the Java collections library and what rust had, but guava has a ton of useful collections/collection implementations.

[Gankro]

Hmm, just noticed that the PriorityQueue in std is a max-heap. Is that what we want? It means insert-all, pop-all outputs in reverse-sorted order (at least wrt the std sort function). That seems counter-intuitive to me. I’d think you’d want the “natural” ordering if nothing else has been specified, no?

[nathantypanski]

If we had a PriorityQueue trait and then MinHeap and MaxHeap be impls of this then that wouldn’t be a problem.

But in general max heaps are useful for e.g. job scheduling. I don’t see a good reason to prefer one over the other by default.

[Gankro]

Maybe we could have a Sorted trait that PriorityQueues and SortedMap/SortedSets provide? It could have three static constructor functions:

• from_fn
• natural_ord
• rev_ord

Where from_fn takes a generic comparator for the type of interest, and natural/rev_ord require that the type implements Ord? Default I guess could pick natural_ord?

[Gankro]

I’ve been working on hacking out nicer set of traits for libcollections, at least as a starting point, but I’ve gotten kind of stuck on iterator-based interfaces. It seems natural to enforce that some kinds of collections should provide some kinds of iterators, so that given a generic instance, you can request an iterator. A lot of default methods could also be provided for plugging together collections if we had this. But it seems impossible to write a good trait for this, at least when the iterator is by value. It seems doable using trait objects, but I’m guessing people wouldn’t be too happy with the structure having to maintain an internal collection of all iterators it has, or heap-allocating the iterators.

Does anyone have any thoughts on this?

[aturon]

Ultimately, we want to provide “associated types” as part of a trait. Something like:

trait Set<A> {
    type Items<'a>: Iterator<&'a A>;
    type MoveItems: Iterator<A>;
    fn iter(&self) -> Items;
    fn move_iter(self) -> MoveItems;
    ...
}

Then each set implementation could provide its own iterator types, and it would all be unboxed.

Unfortunately, trait objects are a problematic workaround not just because of allocation concerns, but also because you can’t call generic methods on them, which rule out a lot of useful Iterator functionality.

So, sadly, I think iterators on these traits will probably need to await a language feature like associated types (there are a couple of other possibilities.) I’m not sure when the feature is likely to happen, but we’re actively thinking about it.

[Gankro]

Oh man, the notion of associated types is really cool! (RFC for those interested). I know I’ve wanted something like that tons of times before in other languages.

I think for now I’ll settle for for_each style methods, with the hope that associate types will save the day be 2.0.

[Gankro]

Okay so I’ve skimmed through a bunch of collection libraries, and here’s my first draft of a new set of traits.

I had to break up some things into separate trait modifiers (searchable, sorted) to capture all the possibilities. In particular, searchable is necessary to determine if an element is in a container, because e.g. that can’t be done on a perfectly generic Vec.

Purposefully excluded multiset/map for laziness/repetitiveness.

Actual names of things are completely arbitrary, some are extra-verbose just to get the idea across without having to write notes.

Probably riddled with genuine mistakes.

[pczarn]

Set trait needs expanding: new implementors: EnumSet, BitFlags

fn intersection(&self, other: &Self) -> Self;
fn intersects(&self, other: &Self) -> bool;
fn union(&self, other: &Self) -> Self;
fn difference(&self, other: &Self) -> Self;
fn symmetric_difference(&self, other: &Self) -> Self;

---

I think SortedMap should be called SortMap because it’s not required to be sorted beforehand, but it’s “Sortable”.

[Gankro]

I think SortedMap should be called SortMap because it’s not required to be sorted beforehand, but it’s “Sortable”.

That’s an interesting perspective on the matter. I had intended SortedMap as “I internally maintain an ordering of the elements, and therefore it is relatively cheap to perform operations associated with ordering”. So your idea is to e.g. allow HashMap to impl a very inefficient SortMap? Or are there some structures you know of that support fast order-based operations that don’t maintain an internal sorting?

[pczarn]

I thought the only requirement was for the values to be PartialOrd so that the map could be Sortable. But it makes more sense to implement it when the worst-case time of min/max is better than O(n).

A trie can support fast order-based algorithms.

[Gankro]

A trie can support fast order-based algorithms.

Isn’t a trie to trees what non-comparison sort is to comparison sort?

Anyway, I’ve taken in some notes from people, and corrected a bunch of errors, so:

Here’s my v0.2 proposal

I’ve rustdoc’d almost everything to better explain why some things are what they are. Also gave some examples of relevant concrete collections to some types/methods. I also try to note places that are dubious or uncertain. Gave reasonable default implementations where possible. They might be wrong.

Docs become a bit less thorough as it goes on, as e.g. the Map interfaces are basically the same as the Container interfaces, but, you know, with keys and values. I also don’t feel like I need to explain the “Stack” trait, because, seriously, it’s a stack.