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

[Dave Abrahams]

on Wed Jul 20 2016, Jonathan Hull <swift-evolution at swift.org> wrote:

>> On Jul 20, 2016, at 3:30 PM, Dave Abrahams <dave at boostpro.com> wrote:
>> 
>> 
>> on Wed Jul 20 2016, Dave Abrahams <dabrahams-AT-apple.com> wrote:
>> 
>
>>> on Wed Jul 20 2016, Jonathan Hull <jhull-AT-gbis.com> wrote:
>>> 
>>>>>>>> Basically, I added back in a super-minimal protocol to fill the
>>>>>>>> structural gap left by Sequence.  I call it “IteratorProvider” and it
>>>>>>>> only has a single function which vends an iterator.  Collection
>>>>>>>> adheres to this, and Iterator adheres to it by returning itself.  All
>>>>>>>> of the other methods from Sequence remain on Iterator.  Thus anyone
>>>> 
>>>>>>>> with API that only needs a single pass would take a IteratorProvider
>>>>>>>> and then work on the iterator it provides.
>>>>>>> 
>>>>>>> That leaves us back where we are now: people will see that
>>>>>>> IteratorProvider is a simple, universal protocol for both single-and
>>>>>>> multi-pass sequences, write algorithm libraries that depend on
>>>>>>> multi-pass-ness, and test them with the most prevalent examples, which
>>>>>>> happen to be multi pass.
>>>>>> 
>>>>>> Let me make a quick counter-argument, because I thought about it a
>>>>>> bit, and I don’t think it does have the same problem (especially with
>>>>>> careful/better naming).
>>>>>> 
>>>>>> The difference is that the ONLY method on IteratorProvider is the one
>>>>>> to get an iterator.  There is no map, filter, sort, first, count, etc…
>>>>>> just a way to get a single-pass iterator.  This changes the mindset
>>>>>> when using it.  You are aware that you are getting a single-pass
>>>>>> iterator.
>>>>> 
>>>>> Maybe.  What's to stop people from extending IteratorProvider?
>>>> 
>>>> Nothing.  But that is true of any protocol.  I am ok with individual's
>>>> extensions.  They would have to use that single method to build up
>>>> from anyway, so presumably they would have to consider the single pass
>>>> case in their extensions...
>>>> 
>>>>>> True, people might try to get the iterator a second time, but we can
>>>>>> make the iteratorProvider method optional (and trying to get an
>>>>>> iterator from an iterator which is spent would return nil) 
>>>>>> and then they are forced to deal with the case where it was
>>>>>> single-pass.
>>>>> 
>>>>> Now you can't loop over the same array multiple times.
>>>> I must be missing something.  Isn’t that the point?
>>> 
>>> No.  Arrays are multipass.
>>> 
>>>> I mean, your version is called “IterableOnce”.  Why do you want to
>>>> iterate on IterableOnce more than once?  
>>> 
>>> Because it happens to be multipass.
>>> 
>>>> The point (at least in my mind) is to provide a common interface for
>>>> things that we want to iterate over a single time.  If you want to
>>>> iterate multiple times, use collection’s interface where you are
>>>> guaranteed multi-pass.
>>> 
>>> for ... in uses Iterators.
>>> 
>>>> That said, you actually can loop multiple times for collections by
>>>> getting a new iterator from the provider (which could point to the
>>>> same array storage).  The optional just forces you to check for the
>>>> single-pass case.
>>> 
>>> Oh, I'm sorry; I didn't realize you were saying that only single-pass
>>> IteratorProviders would ever return nil from their methods.
>> 
>> Note: any IteratorProvider that could return nil would have to be a
>> class (or wrap a class) in order to bypass mutability restrictions,
>> since we can't allow the method that provides the iterator to be
>> mutating.
>
> That is a good point.  I think I am ok with it, since in my mind this
> is already true of non-clonable Iterators anyway.  If you recall, in
> my original proposal I wanted to make iterators reference types. That
> was rejected for performance reasons, but I still think that
> non-clonable Iterators will at least need to wrap a reference type
> somewhere (or they will be subject to the issue you are talking about
> above).
>
> Note: In the current system, it is common to create sequences, but
> under my proposal it would be rare to create an IteratorProvider that
> wasn’t also an Iterator or Collection, since Iterator and Collection
> would both have default implementations satisfying IteratorProvider,
> and IteratorProvider doesn’t have any useful methods besides the one
> providing an Iterator.

Suggestion: Realistically, I see no possibility that this idea can be
completely designed, reviewed, approved, and implemented in time for
Swift 3, so let's take this up after Swift 3 ships.  Yes, it's a
breaking change, but there *will* be some of those going forward.
Obviously, if you disagree, feel free to pursue it now, but—even though
I'm very interested in this topic—I don't
think I have the time budget to participate at the moment.

Regardless, the best proof-of-concept would be to implement it and
create a pull request against Swift that demonstrates how it works and
passes tests, and that can be worked on by anybody at any time.  That's
also the only thing I can imagine that would make it realistic for me to
spend time on it before Swift 3 ships.

-- 
Dave