> On Jun 22, 2016, at 3:57 PM, Dave Abrahams via swift-evolution > <swift-evolution@swift.org> wrote: > > > on Wed Jun 22 2016, David Waite <swift-evolution@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@swift.org > https://lists.swift.org/mailman/listinfo/swift-evolution _______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution