[swift-evolution] [RFC] New collections model: collections advance indices

[plx]

> On Mar 3, 2016, at 3:28 PM, Dmitri Gribenko <gribozavr at gmail.com> wrote:
> 
> On Thu, Mar 3, 2016 at 9:56 AM, plx via swift-evolution
> <swift-evolution at swift.org> wrote:
>> # General Remarks: Great!
>> 
>> Thanks for sharing this proposal; it's a big change, but will be a big improvement once it's in place, and it's encouraging to see the team is willing to undertake changes of such scale.
>> 
>> I'm not sure how much discussion you'll actually manage to scare up b/c the issues this proposal addresses are *not* common, but are nevertheless rather significant when encountered.
>> 
>> E.G.: it's nice to be able to create simple chain/product/etc. collection-combinators which can, themselves, be collections, without winding up with indices indices forced to choose between *either* holding a back-reference to retrieve various startIndex/endIndex values as-needed *or* carrying around a complete set of all needed startIndex/endIndex values.
> 
> Agreed!  We already have that problem in the lazy flatMap collection.
> 
>> I don’t have any negative feedback that isn’t subsumed by the next section.
>> 
>> # Concern: Linearity Baked-In
>> 
>> Even with this change, I have some concern that the proposed protocol hierarchy from `Collection` onward feels like it has a foreseeable lack of generality due to how strongly "linear" the design wants `Collection` to be.
>> 
>> Is this the right time to raise such concerns (e.g. in-scope for this discussion)?
> 
> We can definitely dive into more details about this.  One thing that I
> would want to understand is whether this non-linearity concept could
> be added later without a re-design.

Sorry for the belated reply; I had to think for a bit about this one!

I’m not entirely sure, in part b/c I don’t have a ready-to-go alternative design to propose.

What I had in mind was to try and "reserve room” for alternative indexing schemes to be added later without undue awkwardness.

However, when I went looking for real-world examples of such alternative indexing schemes it seems it’s just not something anyone actually does, and there’s probably a reason for that!

I think it’s possible to adjust the protocol hierarchy to “reserve room”—remove `Indexable`’s methods from `Collection`, add them back to a new `ForwardCollection` between `Collection` and `BidirectionalCollection`—but it’d only make sense to do that if you expect to have use for that room in the future.

> Could you provide more information about the linearity issues that you
> have in mind?  Are you thinking of something like Segmented Iterators
> and Hierarchical Algorithms [1]?
> 
> [1] http://lafstern.org/matt/segmented.pdf

That’s a neat paper! It also seems limited, insofar as it only demonstrated an improved implementation of `fill` (which is somewhat suggestive vis-a-vis the suspicions outlined above).

What I *was* thinking of was something generalizing the chapter on “Bifurcate Coordinates” in Stepanov’s “Elements of Programming” (this approach seems easily generalizable, but that doesn’t seem to have been taken up anywhere).

My thoughts were that as collections get stronger semantics, there’s an increasing disconnect between the semantics of the collection and the semantics of a “linear” index. Working up to it:

Arrays and array-like collections are truly “linear”, and are well-modeled by “linear” indices as-per the proposal; there’s a rich collection of generic algorithms that work on such collections and their indices, and it’s nice to have them in Swift.

Sets and dictionaries (and similar) are what I guess you could call “flat” (or “almost-linear”) collections: iteration aside, many index-based generic algorithms don’t work (particular mutating algorithms), and even where such algorithms *do work* it tends to be like this:

  let stringSet: Set<String> = [“a”, “b”, “c”, “d” ]
  let bPrefix = stringSet.prefixThrough(stringSet.indexOf(“b”)!)

…where the operation is *well-defined* but doesn’t have much to do with the semantics of `Set`.

Collections with even-stronger semantics (tree-shaped collections, order-maintaining collections, geometric collections, etc.) will likely have even further semantic disconnections!

As an example, one thing I’m working on is *basically* a “set" of `(Value,CGRect)` pairs (with the rects possibly-overlapping each other); it keeps its contents organized so you can traverse its contents sorted by any combination of edge (north/south/east/west) and order (ascending/descending).

The way I have been structuring it is that each of those traversals is basically like this:

  extension CustomCollection {

    /// Returns a collection providing a specific, read-only, ordered “view” of the collection's contents.
    var byAscendingNorthernEdges: AscendingNorthernEdgeView { get }

  }

…and although I *did* make `CustomCollection` itself into a `CollectionType`, I can’t think of any scenario in which I’d ever intentionally want to use its `Index` for anything other than iteration.

Similarly, consider something like the tree-index situation vis-a-vis generic algorithms like `binarySearch`, `upperBound`, `lowerBound`, and `equalRange`:

- if the tree *isn’t* ordered-as-required the generic algorithms won’t work b/c the precondition isn’t being met
- if the tree *is* ordered-as-required the algorithms *will* work, but an implementation using linear-indices would likely be sub-optimal vis-a-vis implementations that exploit the tree-structure (start at root, follow appropriate branch, etc.) 

…all of which leads me to wonder a bit about the general usefulness of such linear indices outside of iteration.

To be clear, there’s nothing in all of the above that has anything specifically to do with “Collections move Indices”; it’s all about potential future directions.

Even then, it seems like most other languages stick with what I’ve been calling a “linear” model and their “fancier" collections *are* collections (as per their basic collection-API) and then use additional API to get at the “fancier” functionality, so it’s not clear there’s a real need to do different here.

> 
>> Other than that concern about generality I think this proposal looks great "on paper” and I hope to get a chance to experiment with it soon.
> 
> If you want to try an early version, there is a prototype
> implementation in
> https://github.com/apple/swift/blob/master/test/Prototypes/CollectionsMoveIndices.swift
> 
> Dmitri
> 
> -- 
> main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
> (j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr at gmail.com>*/