on Wed Jun 22 2016, Matthew Johnson <swift-evolution@swift.org> wrote:
>> 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) 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@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 -- Dave _______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution