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

Dave Abrahams dabrahams at apple.com
Wed Jun 22 18:41:58 CDT 2016

on Wed Jun 22 2016, Matthew Johnson <swift-evolution at swift.org> wrote:

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

for..in over an infinite sequence is not necessarily wrong.  I'm not
confident it should be prevented.  It's certainly less dangerous than
using `forEach`, from which there is no possibility of escape.

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

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.

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

Just to keep things straight, let's please adjust one thing at a time.
Adding new concepts should be separated from renaming existing ones.  I
don't want to have to qualify “Sequence” every time I use it in this
thread to clarify whether I mean the existing one or what you're

> `for..in` naturally requires `FiniteIterable`, 

I'm less than confident.  

FWIW, I'm also not entirely confident that single-pass things should be
part of *this* picture at all.  It might be that single-pass things
should be entirely separate and forced to be reference types where
traversal mutates the instance.  E.g., the current Iterator could gain a
class constraint and become the only representation of single-pass

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

These are all potential Collections, AFAICT.  I see no reason they
shouldn't be treated as such.

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

Another reason I'm reluctant.  Whatever we do, IMO, should simplify things.

> 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
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution


More information about the swift-evolution mailing list