[swift-evolution] [Pitch] Remove destructive consumption from Sequence
Andrew Bennett
cacoyi at gmail.com
Wed Jun 22 17:58:57 CDT 2016
Could we have a BufferedSequence type that is identity in most cases?
On Thursday, 23 June 2016, Andrew Bennett <cacoyi at gmail.com> wrote:
> I agree that there should be a type for a non-destructive re-entrant
> sequence.
>
> IIRC in past discussions one of the counter arguments given was IO stream
> sequences. It is likely undesirable to buffer the entire stream, but
> without buffering there's no guarantee of getting the same values.
>
> These discussions were back when swift-evolution started, sorry I couldn't
> find a link. I think it was discussed in the context of a non-mutating
> Generator.
>
> On Thursday, 23 June 2016, Matthew Johnson via swift-evolution <
> swift-evolution at swift.org
> <javascript:_e(%7B%7D,'cvml','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)
>>
>> >
>> >> 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
>>
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160623/ba069bc2/attachment.html>
More information about the swift-evolution
mailing list