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

[Dave Abrahams]

on Thu Mar 03 2016, Dmitri Gribenko <swift-evolution at swift.org> 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.
>
> 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

Awesome paper; everybody should read it ;-)

Collections aren't necessarily about fundamentally linear structures,
but about *linearizable* structures.  If you want to build a system of
generic algorithms that work efficiently on all kinds of data
structures, flat linearity won't always be the most efficient
abstraction, but:

1. It's generally simpler to write linear algorithms (e.g. even copying
   from one hierarchical data structure to another with different
   intermediate segment boundaries can be hard to code).

2. You'll want the linear specialization for the leaves of your data
   structure regardless of what else you do, so having a linearized
   abstraction is important even if you're going to build a hierarchical
   one.

-- 
-Dave