[swift-evolution] Fixing the confusion between non-mutating algorithms and single-pass sequences

[David Waite]

> On Jul 12, 2016, at 4:55 PM, Dmitri Gribenko via swift-evolution <swift-evolution at swift.org> wrote:
> 
> Hi,
> 
> I'd like to continue the discussion of the issue raised by David Waite
> inhttp://thread.gmane.org/gmane.comp.lang.swift.evolution/21295/:
> 
> - Rejected option: remove Sequence, let IteratorProtocol model
> single-pass data streams

I was looking into implementing this as well (although a bit slowly, was on vacation and entertaining house guests). I don’t know if it is worth taking this to a proposal now with this conclusion stated, but I will give my evaluation below:

I took a slightly different approach in prototyping - I made IteratorProtocol require reference types, and made iterator methods lazy by default. I also made AnyIterator a base class for the Iterator objects returned by the default implementations in the IteratorProtocol extensions.

With underestimatedCount and dropFirst as distinct counterexamples, most of the methods did not make sense to include as potential overrides on the protocol. As examples, map() and filter() do not give opportunities for a subclass to optimize a default behavior.

It still made sense for Collection to have a makeIterator, and to act like such an iterator consumed a copy of the collection. As such, an algorithm written for an Iterator could be applied to Collections relatively simply.

Since Iterators were lazy, the duplication wasn’t so much with Collection as with LazyCollection. Methods which took an Iterator or a Collection just called makeIterator on the collection. I felt some of the algorithmic and method duplication was offset by the removal of Sequence and LazySequence, and the ability to internalize the types returned as results from the extension methods.

The last remark I’ll add was that I looked at splitting out certain methods into a FiniteIteratorProtocol; methods like dropLast, suffix, count, etc. I experimented with the API for IteratorProtocol using this in places as well, such as starts(with:) taking a finite iterator as its argument. 

This seemed to definitely lead to an explosion of API complexity, and I decided that it was probably not worth differentiating the two in the class system, and that in fact it might be worth holding off on the finite-targetted methods until it is obvious they are needed, since adding a FiniteIteratorProtocol subclass could be considered additive.

-DW