[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
proposing.
> `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
sequences.
> 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
--
Dave
More information about the swift-evolution
mailing list