{"action":"created","issue":{"url":"https://api.github.com/repos/lampepfl/dotty/issues/818","labels_url":"https://api.github.com/repos/lampepfl/dotty/issues/818/labels{/name}","comments_url":"https://api.github.com/repos/lampepfl/dotty/issues/818/comments","events_url":"https://api.github.com/repos/lampepfl/dotty/issues/818/events","html_url":"https://github.com/lampepfl/dotty/issues/818","id":109750807,"number":818,"title":"Wanted: Strawman proposals for new collections architecture","user":{"login":"odersky","id":795990,"avatar_url":"https://avatars.githubusercontent.com/u/795990?v=3","gravatar_id":"","url":"https://api.github.com/users/odersky","html_url":"https://github.com/odersky","followers_url":"https://api.github.com/users/odersky/followers","following_url":"https://api.github.com/users/odersky/following{/other_user}","gists_url":"https://api.github.com/users/odersky/gists{/gist_id}","starred_url":"https://api.github.com/users/odersky/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/odersky/subscriptions","organizations_url":"https://api.github.com/users/odersky/orgs","repos_url":"https://api.github.com/users/odersky/repos","events_url":"https://api.github.com/users/odersky/events{/privacy}","received_events_url":"https://api.github.com/users/odersky/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":4,"created_at":"2015-10-05T08:22:49Z","updated_at":"2015-10-05T16:10:21Z","closed_at":null,"body":"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:\r\n\r\n 1. Normal usage of collections should stay the same. That is, the standard operations\r\n   on collections should still be available under the same names. Some more exotic and advanced\r\n   scenarios such as `breakOut` can be dropped if alternative ways to achieve the same functionality\r\n   exist.\r\n\r\n 1. 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.\r\n\r\n 1. We should strive for simplicity in APIs and implementations.\r\n\r\n 1. We should strive to better separate interfaces from implementation and avoid the fragile base\r\n   class problem, where too much gets inherited automatically.\r\n\r\n 1. We should try to simplify the inheritance graphs, in particular those of often-used collections\r\n   such as lists.\r\n\r\n 1. 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. \r\n\r\n 1. We should try to integrate Java8 streams and/or have our own high-performance implementations for\r\n   parallel collections.\r\n\r\n 1. 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 `ArrayBuffer`s should be called even if the static types of the operands of `++` are `Iterable`s. \r\n\r\n 1. The design should be friendly to optimizations such as inlining and, possibly, more advanced\r\n   whole program optimizations.\r\n\r\n\r\nTo 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. \r\n\r\nAfter 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.\r\n\r\nBase Traits\r\n----------------\r\n\r\n    Iterator\r\n    Iterable\r\n    Seq\r\n\r\nFor 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).\r\n\r\n`Iterable` and `Seq` are considered collection types, but `Iterator` is not.\r\n\r\nCollection Implementations\r\n------------------------------------\r\n\r\n    List                       \r\n    ArrayBuffer          \r\n    java.lang.String  \r\n    View                 \r\n\r\n`List` is a simplified version of Scala lists. It's an immutable collection favoring linear access patterns. `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.\r\n\r\n`List` and `ArrayBuffer` should have companion objects that let one construct collections given their elements in the usual way:\r\n\r\n    List(1, 2, 3)\r\n    ArrayBuffer()\r\n\r\nCollection operations\r\n----------------------------\r\n\r\nThe following operations should be supported by all collections.\r\n\r\n    foldLeft\r\n    foldRight\r\n    isEmpty\r\n    head\r\n    iterator\r\n    view\r\n    collectAs\r\n\r\n`foldLeft` and `foldRight` are the basis of all sorts of aggregations. `isEmpty` and `head` exemplify\r\ntests 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 `collectAs` could be either of the following:\r\n\r\n    xs.collectAs[List]\r\n    xs.collectAs(List)\r\n\r\nStrawman collections also should support the following transforms:\r\n\r\n    map\r\n    flatMap\r\n    ++\r\n    zip\r\n    partition\r\n    drop\r\n\r\n`map` and `flatMap` together support all monadic operations. `++` and `zip` are examples of operations with multiple inputs. `partition` was chosen over `filter` because it exemplifies transforms with multiple outputs. `drop` was chosen as a typical projection that yields a sub-collection.\r\n\r\nStrawman `Seq`s (but not necessarily `Iterable`s or `View`s) should also support the following operations\r\n\r\n    length\r\n    apply\r\n    indexWhere\r\n    reverse\r\n\r\nSequences 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. \r\n\r\n`ArrayBuffer` should in addition support the following mutation operations\r\n\r\n    +=\r\n    trimStart\r\n\r\nRequired Optimizations\r\n-------------------------------\r\n\r\nThere are a number of possible specializations that the strawman architecture should support. Here are\r\ntwo examples:\r\n\r\n 1. `xs.drop(n)` on a list `xs` should take time proportional to `n`, the retained part of the list should not be copied.\r\n\r\n 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.\r\n\r\nThese specializations should be performed independently of the static types of their arguments.\r\n\r\nWhy No Arrays?\r\n----------------------\r\n\r\nCollections 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. "},"comment":{"url":"https://api.github.com/repos/lampepfl/dotty/issues/comments/145584667","html_url":"https://github.com/lampepfl/dotty/issues/818#issuecomment-145584667","issue_url":"https://api.github.com/repos/lampepfl/dotty/issues/818","id":145584667,"user":{"login":"odersky","id":795990,"avatar_url":"https://avatars.githubusercontent.com/u/795990?v=3","gravatar_id":"","url":"https://api.github.com/users/odersky","html_url":"https://github.com/odersky","followers_url":"https://api.github.com/users/odersky/followers","following_url":"https://api.github.com/users/odersky/following{/other_user}","gists_url":"https://api.github.com/users/odersky/gists{/gist_id}","starred_url":"https://api.github.com/users/odersky/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/odersky/subscriptions","organizations_url":"https://api.github.com/users/odersky/orgs","repos_url":"https://api.github.com/users/odersky/repos","events_url":"https://api.github.com/users/odersky/events{/privacy}","received_events_url":"https://api.github.com/users/odersky/received_events","type":"User","site_admin":false},"created_at":"2015-10-05T16:10:20Z","updated_at":"2015-10-05T16:10:20Z","body":"@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.\r\n\r\n`collectAs` should indeed be `to`; I overlooked that we already have it.\r\n\r\n\r\n"}}