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

[Matthew Johnson]

> On Jun 22, 2016, at 3:57 PM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 
> on Wed Jun 22 2016, David Waite <swift-evolution at swift.org> wrote:
> 
>> Today, a Sequence differs from a Collection in that:
>> 
>> - A sequence can be infinitely or indefinitely sized, or could require
>> an O(n) operation to count the values in the sequence. 
> 
> The latter being no different from Collection.
> 
>> A collection has a finite number of elements, and the fixed size is
>> exposed as an O(1) or O(n) operation via ‘count’
> 
> I don't believe we've actually nailed down that Collection is finite.
> 
> Oh, gee, Nate's documentation edits do
> that. (https://github.com/apple/swift/commit/6e274913)
> Nate, did we discuss this explicitly or did it slip in unnoticed?
> 
> The one crucial distinction in Collection is that you can make multiple
> passes over the same elements.
> 
>> - A collection is indexable, with those indices being usable for
>> various operations including forming subsets, comparisons, and manual
>> iteration
>> 
>> - A sequence may or may not be destructive, where a destructive
>> sequence consumes elements during traversal, making them unavailable
>> on subsequent traversals. Collection operations are required to be
>> non-destructive
>> 
>> I would like to Pitch removing this third differentiation, the option
>> for destructive sequences.
> 
> I have been strongly considering this direction myself, and it's
> something we need to decide about for Swift 3.

I believe this is a problem that should be solved.  

I also believe distinguishing between finite and infinite sequences is a good idea (along with preventing for..in from being used with an infinite sequence)

> 
>> My main motivation for proposing this is the potential for developer
>> confusion. As stated during one of the previous threads on the naming
>> of map, flatMap, filter, etc. methods on Sequence, Sequence has a
>> naming requirement not typical of the rest of the Swift standard
>> library in that many methods on Sequence may or may not be
>> destructive. As such, naming methods for any extensions on Sequence is
>> challenging as the names need to not imply immutability.
> 
> I don't think the names are really the worst potential cause of
> confusion here.  There's also the fact that you can conform to Sequence
> with a destructively-traversed “value type” that has no mutating
> methods.

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

> 
>> It would still be possible to have Generators which operate
> 
> <Ahem> “Iterators,” please.
> 
>> destructively, but such Generators would not conform to the needs of
>> Sequence. As such, the most significant impact would be the inability
>> to use such Generators in a for..in loop, 
> 
> Trying to evaluate this statement, it's clear we're missing lots of
> detail here:
> 
> * Would you remove Sequence?
> * If so, what Protocol would embody “for...in-able?”
> * If not, would you remove Collection?
> * What role would Iterator play?

If we’re going to consider alternative designs it is worth considering the semantic space available.  For the sake of discussion, here is a model that captures the various semantics that exist (the names are just strawmen):

                           Iterable 
                           /          \
                          /             \
                         /               \
    FiniteIterable                 MultipassIterable
                        \                 /
                          \              / 
                           \            /
                          Sequence
                                 |
                                 |
                          Collection

`Iterable` corresponds to the current `Sequence` - no semantics beyond iteration are required.  Infinite, single-pass “sequences” may conform.  

`for..in` naturally requires `FiniteIterable`, but does not require the `MultipassIterable`.

There are many interesting infinite `MultipassIterable` types.  These include any dynamically generated sequence, such as a mathematical sequence (even numbers, odd numbers, etc).  This is also what the existing `Sequence` would become if we drop support for destructive sequences and do nothing else (note: it would still be possible to accidentally write a `for..in` loop over an infinite sequence).

Under this model `Sequence` brings together `FiniteIterable` and `MultipassIterable`.  This describes the most common models of `Sequence`, can safely be used in a `for..in` loop, and does support “destructive” single pass sequences.

`FiniteIterable` and `MultipassIterable` introduce independent and important semantic requirements.  If we’re going to consider changes here, I think it is worth at least considering introducing the distinction.

This is obviously much more complex than than the current design.  The most obvious simplification would be to drop `Iterable` if we don’t have any compelling use cases for infinite, single pass sequences.  One downside to doing this is that the syntactic requirements would need to be repeated in both `FiniteIterable` and `MultipassIterable`

Another obvious simplification would be to also remove `Sequence` (which becomes a “convenience” protocol under this model) and require types that can conform to both `FiniteIterable` and `MultipassIterable` to do so directly.  

If chose to make both simplifications we could also rename the remaining `FiniteIterable` and `MultipassIterable` to something simpler like `Iterable` and `Sequence`.

               (for..in)              (the existing `Sequence` with an additional multipass semantic requirement) 
               Iterable             Sequence  
                        \                 /
                          \              / 
                           \            /
                          Collection

I’m interested in hearing what others think about this way of thinking about the available design space.

-Matthew


> 
> 
> -- 
> Dave
> 
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution