> On Jun 22, 2016, at 7:27 PM, Brent Royal-Gordon <br...@architechies.com> > wrote: > > I think you're tremendously overcomplicating the design.
This isn’t intended as a proposed design. It is intended to start a discussion exploring the design space. > >> 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. > > Okay, so let's start by undoing that renaming to make clear which semantics > in this hierarchy are actually new and which ones are already part of the > standard library. > > Sequence > / \ > / \ > / \ > FiniteSequence MultipassSequence > \ / > \ / > \ / > FiniteMultipassSequence > | > | > Collection Yes, I should have done it this way to begin with. > >> `for..in` naturally requires `FiniteIterable`, > > Why? There's nothing conceptually incoherent about looping over an infinite > sequence. Even ignoring errors, you can `break` out, you can `exit()` from an > interior method, you can abort or fail a precondition, or you can just let it > loop forever. Forbidding potentially-infinite for loops `for` loops is an > arbitrary limitation. The argument for doing this is that `for..in` is syntactic sugar and looping over an infinite sequence using it is often going to be a mistake. I think it’s reasonable to suggest that it be a little be more difficult to write an infinite loop in order to prevent one from doing so accidentally. The position you and Dave have taken is also reasonable. > >> 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). > > Okay, but all of these can be represented as infinite Collections. > > Let me explain. If a Sequence is truly multipass—that is, you can iterate > over it many times and it will always return the same elements—then it must > look something like this: > > struct MyElement { … } > > struct MyState { > … > init() { … } > mutating func formNextElement(in: MySequence) { … } > var currentElement(in: MySequence) -> MyElement? { … } > } > > struct MySequence: MultipassSequence { > struct Iterator: IteratorProtocol { > var sequence: MySequence > var state: MyState > > init(sequence: MySequence, initialState: MyState) { > self.sequence = sequence > self.state = initialState > } > > mutating func next() -> MyElement? { > defer { someState.formNextElement(in: sequence) > } > return someState.currentElement(in: sequence) > } > } > > func formIterator() -> MyIterator { > return MyIterator(sequence: self, initialState: > MyState()) > } > } > > Now, the pieces may *appear* to be different—the Iterator may not actually > need a reference to the Sequence, the state may be stored in many properties > instead of just one, the code to iterate and get the current element may be > directly in `next()` instead of in methods `next()` calls—but any multipass > Sequence and Iterator could be refactored to match this pattern, so all > multipass Sequences and Iterators are equivalent to it. > > But you can convert MySequence into a possibly infinite MyCollection like so: > > struct MyCollection: PossiblyInfiniteCollection { > enum Index: Comparable { > var offset: Int > var state: MyState? > } > > var startIndex: Index { > return Index(offset: 0, state: MyState()) > } > var endIndex: Index { > return Index(offset: Int.max, state: nil) > } > > func formIndex(after index: inout Index) { > index.state!.formNextElement(in: self) > if index.state!.currentElement(in: self) == nil { > index.offset = Int.max > } > else { > index.offset! += 1 > } > } > > subscript(index: Index) -> MyElement { > return index.state!.currentElement(in: self) > } > } > > func == (lhs: MyCollection.Index, rhs: MyCollection.Index) -> Bool { > return lhs.offset == rhs.offset > } > > func < (lhs: MyCollection.Index, rhs: MyCollection.Index) -> Bool { > return lhs.offset < rhs.offset > } > > In other words, whatever state (other than the sequence itself) the Iterator > needs to keep in its stored properties can instead be stored inside an index, > and whatever logic the Iterator needs to implement its `next()` method can > instead be split between `formIndex(after:)` and `subscript(_:)`. Any > MultipassSequence can be written as a PossiblyInfiniteCollection if you're > willing to put in the effort. And this is a boon to its multipass-ness, > because you can not only start over again from the beginning, but start over > from *any* step in the iteration. > > If any MultipassSequence can be written as a PossiblyInfiniteCollection, then > we can eliminate another protocol: > > Sequence > / \ > / \ > / \ > FiniteSequence PossiblyInfiniteCollection > \ / > \ / > \ / > Collection > > Now we can move any members which may not terminate early (like `map` or > `last`) or are ill-defined when infinite (`count`) into `FiniteSequence` and > `Collection`, while leaving any which often do terminate early (like `first` > or `index(of:)`) in `Sequence` and `PossiblyInfiniteCollection`. > > Is this necessary? I don't really know. Arguably, we could simply provide > this hierarchy: > > Sequence > / \ > / \ > / \ > IteratorProtocol Collection > > Where Iterators must be treated as potentially infinite, Collections are > always finite, and you are asked (or, with a "closed protocol" feature, > forced) to conform to one or the other, rather than to Sequence directly. > Then the non-infinite-safe APIs like `map` can move onto `Collection` and > we'll have covered most of the use cases which matter. Thanks! This is exactly the kind of discussion I intended to encourage with my post. This looks pretty good to me but it doesn’t address the issue that initiated this thread - removing destructive consumption (non-multipass) from Sequence. How do envision that fitting in? Can you also elaborate on what you envision `IteratorProtocol` would look like in this picture? You depict it refining `Sequence`. That is not the current design in the standard library so it isn’t immediately clear to me. -Matthew > > -- > Brent Royal-Gordon > Architechies > _______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution