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

[David Waite]

> 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.

1. we could use integer indexes and use a non-recursive technique for calculating the fibonacci value at the specified index. FibIterator basically is rewritten into a function “fibonacci(at index:Int)”.

2. We could use a copy of FibIterator as the index, since it is a value type. FibIterator would need to implement Comparable.

	2a. We make the index InfiniteSequenceIndex< FibIterator >, where the wrapper is there to define a consistent EndIndex value.

	However, Collection’s index(_:offsetBy) allows for negative offsets, which would not be accomplished in O(n).

	2b. If FibIterator gains an extra method to become bidirectional we can support index(_:offsetBy) in O(n) time. Note that you would probably want to have a bidirectional iterator define its own endIndex.

-DW
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160624/1954dd8f/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 496 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160624/1954dd8f/attachment.sig>