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

[Jonathan Hull]

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


Thanks,
Jon