[swift-evolution] [Pitch] Remove destructive consumption from Sequence

[Dave Abrahams]

on Fri Jul 01 2016, Matthew Johnson <matthew-AT-anandabits.com> wrote:

>> On Jul 1, 2016, at 11:07 AM, Dave Abrahams <dabrahams at apple.com> wrote:
>> 
>> 
>> on Fri Jul 01 2016, Matthew Johnson <matthew-AT-anandabits.com> wrote:
>> 
>
>>>> On Jun 30, 2016, at 5:32 PM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
>>>> 
>>>> 
>>>> on Thu Jun 30 2016, Xiaodi Wu <xiaodi.wu-AT-gmail.com <http://xiaodi.wu-at-gmail.com/>> wrote:
>>>> 
>>>>> If Iterators become reference types that model single-pass sequences and
>>>>> becomes for-in-able, as the write-up suggests, couldn't Sequence be
>>>>> stipulated to be multipass and retain its refinement relationship with
>>>>> Collection?
>>>> 
>>>> AFAIK there is no interesting multipass Sequence that cannot reasonably be
>>>> made to support indexing.
>>>> 
>>>> There *is* existing code that exposes multipass data structures without
>>>> exposing the ability to compare iteration state for equality.  
>>> 
>>> It’s worth noting that indices require comparability, not just
>>> equality.  I think comparability might cause more difficulty than
>>> equality (but haven’t thought too hard about it).
>> 
>> It does, but I am ever more strongly motivated to drop the comparability
>> requirement.
>
> Dropping that would eliminate the questions that are still lingering
> in my mind about getting rid of `Sequence`.
>
> Are there any important algorithms that rely on the ability to compare
> indices?

No.  When the collection has random access, you can always measure
distance using the collection and use its sign.  Algorithms that depend
on that ability all require random access anyawy.  If the collection is
not random-access but the Index type is comparable, you can use that as
well, which may make some new things possible.

>>>> In every case I can think of, index equality could easily have been
>>>> exposed, but wasn't.These designs can't be adapted to model
>>>> Collection.
>>> 
>>> Why can’t they be adapted to model Collection if equality could have
>>> been exposed?  Is it because comparability would be difficult?
>> 
>> Comparabile refines Equatable, so it's at *least* as hard ;-)
>
> Right.  You only mentioned that index equality could have been exposed
> but didn’t mention comparability.  I was wondering whether the
> potential additional difficulty is why they couldn’t model Collection.
>
>>>> Those designs are real, but I am unconvinced they are worth supporting
>>>> directly with a separate protocol in the standard library; I'm willing
>>>> to accept the idea that those data structures will simply be limited to
>>>> modeling Iterator.
>>> 
>>> Can you elaborate on what designs / data structures you’re talking
>>> about here?
>> 
>> Cocoa Dictionaries and Sets are examples.  The enumeration interface
>> doesn't have any facility for copying or comparing enumeration state.
>
> What impact would that have on the bridged value types (which is how
> we should be using those in Swift).

None.  Today we have a horrible workaround in Swift to make those model
Collection: storing an array of keys.  At some point we can get
Foundation to do do something friendlier for us, but in the meantime,
that still works.

-- 
Dave