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

[Dave Abrahams]

on Fri Jun 24 2016, David Waite <david-AT-alkaline-solutions.com> wrote:

>> On Jun 22, 2016, at 5:41 PM, Dave Abrahams via swift-evolution
> <swift-evolution at swift.org> wrote:
>> 
>>> I agree, names are not the primary issue.
>>> 
>>> Another issue is that you cannot currently write generic code that
>>> might need to iterate a sequence more than once.  You currently
> have
>>> to over-constrain types to `Collection` even if you don’t need to
> do
>>> anything other than iterate the elements (the discussion about
> whether
>>> `LazyFilterSequnce` has a bug in its `underestimateCount` is
> relevant
>>> here).
>> 
>> That's not an over-constraint.  Multi-pass-ness *is* the fundamental
>> distinction between Sequence and Collection.  AFAIK there's no
> multipass
>> sequence that cannot support indices.
>
> Just wanted to communicate more around this point specifically. If
> Collections can be infinite (probably adding special meaning to count
> returning Collection.IndexDistance.max), then the only difference
> between Sequence and Collection is the indexes.
>
> However, I’m concerned about the delta between an iterator and a full
> collection. For an example:
>
> class FibIterator : IteratorProtocol {
>   var last = 0, current = 1
>
>   func next() -> Int? {
>     (last, current) = (current, current + last)
>     return current
>   }
> }
>
> If subscript indexing on collections isn't required to be an O(1)
> operation, I don’t see a reason for Sequence to exist - we can simply
> enumerate the sequence with a numeric index, and iterate up to that
> count to resolve. But this makes things surprising for those
> implementing generic algorithms across Collections.
>
> I don’t see a way to get an O(1) integer index and meet all the
> efficiency constraints of Collection without either memoization or
> additional complexity on implementing FibIterator.

Indices don't have to be integers, and often arent.  You can always
bundle an integer with an Iterator and a single result buffer to produce
an Index.

-- 
-Dave