Wanted: Strawman proposals for new collections architecture

[odersky]

A redesign of the standard library is on the roadmap for one of the next Scala versions (could be as early as 2.13). Some requirements for the redesign should be:

1. Normal usage of collections should stay the same. That is, the standard operations
   on collections should still be available under the same names. Some more exotic and advanced
   scenarios such as breakOut can be dropped if alternative ways to achieve the same functionality
   exist.
2. User-defined implementations of collections should port to the new library as far as is reasonable. We should allow some breakage here, if it is necessary to achieve other goals.
3. We should strive for simplicity in APIs and implementations.
4. We should strive to better separate interfaces from implementation and avoid the fragile base
   class problem, where too much gets inherited automatically.
5. We should try to simplify the inheritance graphs, in particular those of often-used collections
   such as lists.
6. We should improve the integration of strict and lazy collections by means of a better architecture for views. Views should avoid accidental forcing, and should omit transforms from collections that require such forcing. However, forcing is still needed to support aggregations.
7. We should try to integrate Java8 streams and/or have our own high-performance implementations for
   parallel collections.
8. We should generally be at least on par with current collections in what concerns efficiency. In particular, we should still allow specializations of collection operations for particular implementations. These optimizations should still work if the static collection type is abstract. E.g. an optimized implementation of ++ on ArrayBuffers should be called even if the static types of the operands of ++ are Iterables.
9. The design should be friendly to optimizations such as inlining and, possibly, more advanced
   whole program optimizations.

To gain experience it would be good to experiment with some prototypes that illustrate possible designs and can point to strengths and weaknesses. A full collections design is too heavy to fill this role. It takes too long to write and understand. As an alternative, I propose to implement just a subset of the required functionality. The subset should implementable in about 500 LOC or less and at the same time should be as representative as possible of the whole collections. The API should be the same for all strawman proposals.

After some experimentation, I came up with the following proposal for the API to be implemented by strawman proposals. There's still some modest room to add things if people feel it is important.

Base Traits

Iterator
Iterable
Seq

For now we leave out maps and sets (which does not say they are not important). We gloss over the mutabile/immutable distinction. All collections are in the same package (this is only for the strawman, to keep things simple, not for the full collections, of course).

Iterable and Seq are considered collection types, but Iterator is not.

Collection Implementations

List                    
ListBuffer   
ArrayBuffer          
java.lang.String  
View                 

List is a simplified version of Scala lists. It's an immutable collection favoring linear access patterns.
List operations should be tail-recursive, hence the addition of ListBuffer to hold intermediate results. ArrayBuffer is a mutable collection that supports random access. String should demonstrate how the architecture integrates externally defined types. String should be seen by Scala as an immutable random access sequence of Char. Finally, views should be constructible over all other collections. They are immutable and lazy.

List, ListBuffer and ArrayBuffer should have companion objects that let one construct collections given their elements in the usual way:

List(1, 2, 3)
ListBuffer("a", "bc")
ArrayBuffer()

Collection operations

The following operations should be supported by all collections.

foldLeft
foldRight
isEmpty
head
iterator
view
to

foldLeft and foldRight are the basis of all sorts of aggregations. isEmpty and head exemplify
tests and element projections. iterator and view construct iterators and views over a collection. collect is not part of the current Scala collections, but is useful to support views and Java 8 streams. It should construct a new collection of a given type from the elements of the receiver. An invocation pattern of to could be either of the following:

xs.to[List]
xs.to(List)

Strawman collections also should support the following transforms:

filter
map
flatMap
++
zip
partition
drop

map and flatMap together support all monadic operations. ++ and zip are examples of operations with multiple inputs. drop was chosen as a typical projection that yields a sub-collection. partition was chosen in addition filter because it exemplifies transforms with multiple outputs.

Strawman Seqs (but not necessarily Iterables or Views) should also support the following operations

length
apply
indexWhere
reverse

Sequences in a way are defined by their length and their indexing method apply. indexWhere is an example of a method that combines indices and sequences in an interesting way. reverse is an example of a transform that suggests an access pattern different from left-to-right.

ArrayBuffer and ListBuffer should in addition support the following mutation operations

+=
++=
trimStart

Required Optimizations

There are a number of possible specializations that the strawman architecture should support. Here are
two examples:

1. xs.drop(n) on a list xs should take time proportional to n, the retained part of the list should not be copied.
2. xs ++ ys on array buffers xs and ys should be implemented by efficient array copy operations. s1 ++ s2 on strings should use native string concatenation.
3. partition should require only a single collection traversal if the underlying collection is strict (i.e., not a view).

These specializations should be performed independently of the static types of their arguments.

Why No Arrays?

Collections definitely should support arrays as they do now. In particular, arrays should have the same representation as in Java and all collection operations should be applicable to them. Arrays are left out of the strawman requirements because of the bulk their implementation would add. Even though no explicit implementation is demanded, we should still check all designs for how they would support arrays.

[nilskp]

It's not clear if Sets are considered part of "collections" (since they're left out), but a number of operations are questionable for sets, e.g. map (can unexpectedly lead to reduction in resulting set) and zip (implies some order).

[odersky]

@nilskp This is answered by requirement (1): normal usage of collections should stay the same. So, yes, map and zip will continue to work on sets. At least I would classify map over sets as normal usage, maybe zip is debatable. On the other hand, zip is useful. What's to object against set.zipWithIndex as a way to arbitrarily assign set elements unique indices?

[soc]

Some minor bits, which might be interesting despite all the fundamental objections I have to this:

• If we can't find a more sophisticated way to deal with collection size, at least move size to Long.
  This can be done by telling people to either migrate to length or by encouraging them to start adding type ascriptions of : Long to code calling size now.
• I have found that groupBy is a good benchmark of collection design, maybe it could be added to the list of required methods for the prototype.
• What is collectAs[C] and what's the difference to to[C]? Feels like a poor name given that collect dos something completely different, a lot like mapTo in some other API.

[odersky]

@soc Agree that groupBy is a good benchmark. It means we have to add maps to the base traits. I did not do it in version 1 in order to keep the scope small. But it's a prime candidate for version 2.

collectAs should indeed be to; I overlooked that we already have it. I updated the text.

[odersky]

@soc The collection size type is a separate issue. Important to discuss this too, I agree.

[nilskp]

@odersky, but it should be trivial to "cast" set to a collection that supports map and zip and thus avoid any potential pitfalls, no?

[odersky]

@nilskp How do you "cast"? But I think we should take this discussion elsewhere it is out of scope for the strawman discussion. Or, more productively: How about writing a strawman implementation that includes sets? Then we can see how that would work out.

[machisuji]

Not realizing I was mapping a Set has tripped me on a number of occasions too. Everyone else does it too, though (Haskell, Python). Haskell at least has a special comment on map for Set pointing out that the resulting set's size may be smaller.

I find zip on Sets makes sense just like toSeq where people have to realize that the order is not defined.

Edit: But you are right that this is besides the point for now. Moving on.

One point I'd like to add is that it would be nice if it was easy to create one's own abstract collection operations while retaining the type of the concrete collection. Last time I tried this it seemed relatively complicated. Though I do realise that it's not an easy issue to begin with.

[soc]

@machisuji I think the issue with Set will only be a problem, if we keep trying to pretend that every intermediate operation is a Set. Given that we know all the drawbacks of that, like:

• Operations are evaluated immediately, causing unnecessary and excessive computations of things which were never requested at the end, memory overhead due to allocation of intermediate data-structures and garbage collection churn.
• It requires that all individual classes implement the whole API, making the API extremely heavyweight, and hard to grasp, contributing to the large foot-print of the collections library.
• For some things like "Streams", providing the implementation is somewhere between "extremely hard" and "a complete nightmare".
• It requires the invention of "views" as a secondary API, which try to act a little bit smarter, but are almost never used due to the syntactic overhead in usage and the lack of polish. If the new collection API needs separate "views", our design is not good enough.

[viktorklang]

I'd like to explore the idea that a collection is data, and then you apply transformations to it, and transformations can be composed separately from the data (think: transducers), macros could them be used to very efficiently inline these operations.