[swift-evolution] [Pitch] Remove destructive consumption from Sequence
Andrew Bennett
cacoyi at gmail.com
Wed Jun 22 17:54:36 CDT 2016
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> wrote:
>
> > On Jun 22, 2016, at 3:57 PM, Dave Abrahams via swift-evolution <
> swift-evolution at swift.org <javascript:;>> wrote:
> >
> >
> > on Wed Jun 22 2016, David Waite <swift-evolution at swift.org
> <javascript:;>> 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 <javascript:;>
> > https://lists.swift.org/mailman/listinfo/swift-evolution
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org <javascript:;>
> 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/0b6140ba/attachment.html>
More information about the swift-evolution
mailing list