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.

[nilskp]

@odersky, I meant something like toSeq/toList/etc.

What's to object against set.zipWithIndex as a way to arbitrarily assign set elements unique indices?

The fact that Set doesn't have an index? It might be nitpicking, but 1) I've never had the use case, 2) if I did, I'd prefer to use set.toSeq.zipWithIndex, which makes the intent clear.

[viktorklang]

An AnyVal Option type would be preferred for collections as well. (think Map.get etc)

[lihaoyi]

We gloss over the mutabile/immutable distinction

We probably want mutable collections to not have the same API as the immutable ones. One large problem with the current mutable collections is that by inheriting all the immutable methods, it's neigh impossible to figure out where the "useful" mutable methods are. e.g. Buffers append/remove is what you generally care about, but they're lost in the huge sea of immutable methods you basically never want. The same applies to mutable.Set, mutable.Queue, etc.

By that logic, ArrayBuffer probably shouldn't be a collection, and perhaps making it convertible to one through .view or .iterator is enough?

Views should avoid accidental forcing, and should omit transforms from collections that require such forcing. However, forcing is still needed to support aggregations.

What's the advantage of Views over using Iterators? That's what I've been using when I want to fuse map/filter/flatmap/etc. operators into constant-memory and it seems to work. You don't accidentally force because the only forcing operations are relatively obvious (reduce, sum, fold, foreach, toXXX).

List
ArrayBuffer
java.lang.String
View

Should we add Vector to that list? That's basically the current go-to immutable collection for a lot of things where you want less pointer-chasing than lists and more generic operations (prepend, insert, remove, ...) so I'd want to know where it fits in a "new world"

[viktorklang]

@lihaoyi Yes, having scala.collection.{Seq, Map, … } as a shared hierarchy between mutable and immutable is not beneficial IMO. Same goes for the deep embedding of Parallel Collections into the hierarchy. And The XOnce-things, if you need a XOnce you use an Iterator.

[DarkDimius]

@lihaoyi @viktorklang the current designs that we had a look into follow your proposals.
The data is separate and operations are added to the data through implicit decorators.

The advantage is that most operations(map\flatmap\reduce\zip) do not care if underlying collection is mutable or not.

[DarkDimius]

@viktorklang @lihaoyi , what's your take on deep embedding of views into collections hierarchy?

[SethTisue]

We gloss over the mutable/immutable distinction

The way the old collections gloss over this is one of the paramount issues I would hope to see addressed in any new design.

[viktorklang]

@DarkDimius With a transducer approach I don't see the need for views at all since the primary need for views is to avoid intermediate representations.

@SethTisue 👍

[DarkDimius]

@viktorklang In my understanding, Iterators should be minimal: next \ hasNext and maybe split are the only methods that I would like to have in Iterator.
Unlike this, a View could be a simple decorator over an iterator that adds other operations.

[viktorklang]

@DarkDimius With a transducer approach there's (as far as I can tell) no need for Views—you'd apply the transducer of your choice to the collection of your choice at the time you need it. Did I misunderstand you?

[odersky]

It's great to have the debates, but I think for the purpose of this issue, requirement (1) is non-negotiatable. If we really change fundamentally how users interact with collections, how do we even consider migration and backwards compatibility? It would be a completely separate discussion (which we might want to have). But on this issue I'd like to keep the discussion focussed. How about I open a thread on scala-debate and everybody chimes in there for stuff outside the requirements presented here?

[viktorklang]

@odersky The way that virtually all modern platforms have done this in the past is to introduce a new library/package and include forwarders for the old library/package, is there a reason why this wouldn't be preferable in this case too? I'm assuming that there won't be enough time to arrive at a battle-proven new library unless there is a transitional period where one can fall back to the old library?

[lihaoyi]

Unlike this, a View could be a simple decorator over an iterator that adds other operations.

That sounds great!

In general, the high-level "interface" @odersky describes leaves out a lot of (what would be) crucial scaladoc. Sure, we have Iterators, Iterables and Seqs, and Views, but what are these things? What are they meant to represent, in english? What are their invariants and how are they meant to be used? Is the data-operation separation you described part of the required interface?

[odersky]

Here's the thread on scala-debate:

https://groups.google.com/forum/#!topic/scala-debate/Z1YH_0Hgu5A

All discussions that fall outside requirements 1-9 should go there. I would like to reserve this issue for concrete proposals that try to address the requirements as outlined.

[jedws]

@SethTisue your comment seems at odds with goal 3. Particularly in terms of making methods total which simplifies things significantly.

[pathikrit]

@SethTisue 😿

[bvenners]

I think it may be possible to model non-emptiness in the types while still adhering to "Normal usage of collections should stay the same. That is, the standard operations on collections should still be available under the same names" by leaving the partial methods in place but with a deprecation warning. I won't be sure until I try, but I will try it once I get time to write some code.

[mdedetrich]

@SethTisue your comment seems at odds with goal 3. Particularly in terms of making methods total which simplifies things significantly.

I think you are misunderstanding point 3. Point 3 seems to be mainly about keeping the API simple, and not about subjective use cases of simplicity from modifying the API for reasons of totality (or other reasons).

Simple is not the same thing as correctness, or totality. They are orthogonal concepts

I think it may be possible to model non-emptiness in the types while still adhering to "Normal usage of collections should stay the same.

Not sure how this can work, as far as I am aware, you can't have methods with the exact same parameter signatures return different types (i.e. Option[T] versus the original T)

[bvenners]

Not sure how this can work, as far as I am aware, you can have methods with the exact same
parameter signatures return different types (i.e. Option[T] versus the original T)

I think you meant you cannot have methods with the same parameter signatures but different return types. That's true you can't overload that way. You can have a differently named method though, for example we already have headOption in addition to head.

I'd rather not write English about it but Scala, but the way I modeled "inhabitedness" (to give a more positive name for non-emptiness) is to make a subtype. The subtype has a head method, the supertype does not, but if this were ever to happen in the standard library, there would be a long deprecation period in which the supertype still had head, tail, and reduce. I did a proof-of-concept for just head on Set here:

https://github.com/scalatest/scalatest/blob/feature-equasets/scalactic/src/main/scala/org/scalactic/Collections.scala#L1690

That's inside an instance that captures an Equality typeclass, which also won't work for the standard library, but the subtype technique might still work. I won't know until I try it. It may turn out to not work, and even if it does work, it may be not be appropriate for the standard library. Still I will try it and see where it leads.

One thing I haven't tried, which I'm looking forward to trying, is making a List where the Cons cell subtype has a type alias inhabited.List, and that's how it works on List. So I think for List it might actually be pretty practical even in the standard library. But for everything else, you'd end up with an extra type for everything, and that's a lot of extra surface area. Maybe it could just be List that gets it in the standard library.

Anyway, already too much English. Not enough Scala.

[mdedetrich]

I think you meant you cannot have methods with the same parameter signatures but different return types.

Yup, just edited the post now, my bad!

[japgolly]

I think you meant you cannot have methods with the same parameter signatures but different return types.

Actually you can, using implicits and dependant types. Imagine something like

trait FailureStyle[T] {
  type Result
  def pass(t: T): Result
  def fail: Result
}
def gimme[T](implicit f: FailureStyle[T]): f.Result = ???

// and an implicit like one of these in scope
implicit def throws[T] = new FailureStyle[T] { type Result = T; …}
implicit def option[T] = new FailureStyle[T] { type Result = Option[T]; …}
implicit def returnNull[T >: Null] = new FailureStyle[T] { type Result = T; …}

[bvenners]

Actually you can, using implicits and dependant types. Imagine something like

Good point. Jon Pretty has something similar to the failure modes in your example in Rapture. Here's another example of that sort of technique:

https://github.com/scala/scala/blob/v2.11.2/src/library/scala/collection/TraversableLike.scala#L238

The result type of map depends on which CanBuildFrom instance is chosen implicitly at the call site. So sometimes when you map a Map you get a Map, other times an Iterable. But regardless I wouldn't want to go down the path of letting people pick a "head result policy" in any collection library, especially not the standard library. It is too clever.

[jedws]

@mdedetrich

Simple is not the same thing as correctness, or totality. They are orthogonal concepts

The lack of correctness or totality makes things more complicated (or less simple). This is easy to demonstrate.

Take List[A].head for example it has the type List[A] => A. Given that types are (equivalent to) propositions, we now have a proposition that is false; given a List we cannot always produce a value. We can no longer rely on the type to describe to us whether our program is correct or not, and unless we add additional manual back-of-the-envelope reasoning and code we now have an incorrect program. The true type for getting a value from a List is something like List[A] => A => A.

I suggest you watch Ken Scambler's excellent video for a more detailed description of why partiality increases complexity https://www.youtube.com/watch?v=yS4Dbb1KfmA. Or Philip Wadler's Propositions as Types https://www.youtube.com/watch?v=IOiZatlZtGU on why totality matters for types.

[mdedetrich]

The lack of correctness or totality makes things more complicated (or less simple). This is easy to demonstrate.

Your stating this as an axiom when it isn't one

Take List[A].head for example it has the type List[A] => A. Given that types are (equivalent to) propositions, we now have a proposition that is false; given a List we cannot always produce a value. We can no longer rely on the type to describe to us whether our program is correct or not, and unless we add additional manual back-of-the-envelope reasoning and code we now have an incorrect program. The true type for getting a value from a List is something like List[A] => A => A.

Using your logic, List should return a disjunction of type Either, because its theoretically possible for it to fail due to memory constraints. So according to you, making all List operations have something of type Either[T,Failure] would be more simple. I would hardly agree this makes using a List more simple, but it does make it more correct.

You are arguing about correctness, not simplicity. There isn't a one to one correlation between them. You can make things so simple that they are very hard to get correct (assembly), and you can emphasis correctness so much that things are no longer simple (try writing a generic program in Coq)

In any case, this is getting to be off topic. The scope for the SLIP has already been defined, and you are redefining simple as correct

[japgolly]

Using your logic, List should return a disjunction of type Either, because its theoretically possible for it to fail due to memory constraints.

I don't think that's the kind of strawman meant in "Wanted: Strawman proposals".

[mdedetrich]

I don't think that's the kind of strawman meant in "Wanted: Strawman proposals".

Of course not, but than you can argue the same thing about @jedws proposal. The point being made is that correctness is not the same thing as simple, and they are not directly comparable, which is addressing point 3, i.e.

We should strive for simplicity in APIs and implementations.

[japgolly]

Of course not, but than you can argue the same thing about @jedws proposal.

No mate. I honestly can't find a way to interpret @jedws's points as strawman. It's a valid point and I disagree with this false dichotomy you're trying to draw. It's not true that correctness will always prevent simplicity. It doesn't have to be the case here either.

[mdedetrich]

It's a valid point and I disagree with this false dichotomy you're trying to draw. It's not true that correctness will always prevent simplicity. It doesn't have to be the case here either.

This is a strawman, I was never making a false dichotomy. My point is that an excessive use of correctness can actually harm simplicity, not help improve it.

It doesn't have to be the case here either.

Don't disagree with this, but I was never making this point...

[jedws]

Using your logic, List should return a disjunction of type Either, because its theoretically possible for it to fail due to memory constraints. So according to you, making all List operations have something of type Either[T,Failure] would be more simple. I would hardly agree this makes using a List more simple, but it does make it more correct.

No, within any logic there are some things that are taken as axiomatic. Within computing, appropriate resource availability and correctness of underlying hardware and environment is usually one of them (unless you're building OSs).

Your argument mistakenly conflates non-deterministic runtime problems, with things that are deterministically provable and essentially says, "well, you can't prove all the things, so bugger it, don't bother proving anything". I am not averse to this argument, it is essentially the argument against type systems, but don't think it has much place within the design of strongly typed APIs.

The central point remains, introducing non-determinism, or falsity, or incorrectness, does actually increase complexity.

[SethTisue]

Please take this discussion to another forum such as scala-debate.

[balefrost]

As somebody who writes C# at work and Scala at home, there are some conveniences in the .NET collection API that I miss in Scala. I realize that most of the discussion here is related to the implementation details of the collections library, whereas my comments are more concerned with the user API of the collections library. Still, maybe these thoughts will be useful.

Suppose I have a list of pairs (to be interpreted as key/value pairs). I'd like to group the values by their corresponding keys, with the understanding that there may be duplicate keys. In Scala, I would do that like this (unless there's a simpler way that I'm not seeing):

pairs.groupBy(_._1).mapValues(_.map(_._2))

Or, to be more verbose but perhaps also more efficient, I might do this:

pairs.foldLeft(Map.empty[K, Set[V]]) {
    case (acc, (k, v)) =>
        acc + (k -> acc.getOrElse(k, Nil) :+ v)
}

Whereas in C#, I could use an overload of GroupBy do this:

pairs.GroupBy(x => x.Item1, x => x.Item2)

The .Net library realizes that simultaneous mapping while grouping is a common use case, so they provide a way to do that. The C# version feels far more ergonomic to me than either Scala snippet.

Another nice feature of the .Net collection API is that all methods that iterate the collection with a callback have overloads whose callback function takes the current index. So while I would need to do this in Scala:

coll.zipWithIndex.map {
    case (el, idx) =>
        el * idx
}

I could do this in C#

coll.Select((el, i) => el * idx)

It's easy enough for Select, SelectMany, and friends to also track the index while iterating, so they provide overloads exposing that functionality.

The .Net collection API includes many such conveniences. It's clear that the designers put a lot of thought into it. And though having methods take multiple function parameters seems like a questionable idea, in practice, it works out surprisingly well.

I realize that I'm arguing for convenience, which goes somewhat against goal #3, above. I also realize that the sort of convenience methods that I'm talking about could be implemented by a third-party library. But I believe that the Scala collection library would be better for having these conveniences built-in.

[Blaisorblade]

whereas my comments are more concerned with the user API of the collections library. Still, maybe these thoughts will be useful.

It sounds interesting (and I've run into the first problem myself), but that's also more in scope for the scala-debate discussion. (Also, I think in Scala you'd want to have different method names — IIRC if you overloaded groupBy, the type of x in groupBy(x => ...) would not be inferred).

[SolomonSun2010]

As a reference or Joke: Collection Development Philosophy (web.library.yale.edu/policy/collection-development-statements )

[SolomonSun2010]

I really expect LazyList or Stream add these powerful and convenient methods :
repeat/cycle, repeatedly/generate, iterate, unfold, resource, reject,
like in Elixir and Clojure: https://hexdocs.pm/elixir/Stream.html#unfold/2
This symbol #:: is too low,strange to verbose,unreadable.
Also, I hope add some xxxIndexed like in Kotlin Sequence: https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.sequences/index.html
I think, one of the programming trend is the Lazy Sequences .

[pnf]

I can't figure out where this discussion ended up on transducers (mentioned first above by @viktorklang ), but it seems like it wouldn't be hard to compose Views with some sort of ViewTransformer[-A,+B]. For example, like this.
This separates the composition of combinators from application to a specific collection, which is accomplishes one of the goals of transducers. We don't get the (supposed) benefit of JIT optimization of literal function composition of transformations of reducing functions.

POC in scala/collection-strawman#144

[smarter]

Closing since this discussion has gone stale. Discussions related to the main collection strawman proposal should go in https://github.com/scala/collection-strawman. More general discussions should probably move to https://contributors.scala-lang.org .