<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Jan 6, 2016, at 10:42, plx via swift-evolution <<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><blockquote type="cite" class=""><div class=""><br class="Apple-interchange-newline">On Jan 6, 2016, at 11:37 AM, Jordan Rose via swift-evolution <<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div class="">I've bounced this idea off of Dave and Dmitri internally, so might as well put it out publicly:</div><div class=""><br class=""></div><div class="">In Magic DWIM Swift, there would only be two types that you'd ever conform to: a destructive iteration type (today's "Generator"), and a multi-pass indexed type (today's "Collection"). Some <i class="">operations</i> can meaningfully use either one (like forEach or maxElement); these operations go on a general "traversable" type (today's "Sequence").</div><div class=""><br class=""></div><div class="">In this world, both GeneratorType and CollectionType are refinements of SequenceType (i.e. any GeneratorType "is-a" SequenceType), including the necessary default implementations. Maybe we rename some of the protocols in the process. Again, no concrete type would ever conform to SequenceType; it's just something you can use as a generic constraint.</div><div class=""><br class=""></div><div class="">We can't actually do this today because it creates a circularity between SequenceType and GeneratorType that the compiler can't handle. I'm pretty sure it's possible to change the compiler's protocol checking logic to allow this, though.</div><div class=""><br class=""></div><div class="">Anyway, that's that idea. At the very least it helped me clear up my thoughts about Sequence, Collection, and Generator back when I was first learning them.</div><div class=""><br class=""></div><div class="">Jordan</div><div class=""><br class=""></div><div class="">P.S. This idea falls apart if someone comes up with a model (concrete type) for SequenceType that isn't a Collection or Generator. I wasn't able to think of one back when I was originally thinking about this, but of course that doesn't mean there isn't one. (Infinite collections are interesting as discussed on the "cycle" thread, but it's not the sequence/generator distinction that's really meaningful there.)</div></div></div></blockquote><div class=""><br class=""></div><div class="">It’s not clear what you mean by a `SequenceType` that isn’t either a `Collection` or a `Generator`, but if you mean a *concrete* sequence that:</div><div class=""><br class=""></div><div class="">- can be re-iterated (thus not a `Generator`)</div><div class="">- has no meaningful index (!) (thus not a `Collection`)</div><div class=""><br class=""></div><div class="">…then I can provide you with examples of such. The (!) is b/c you can of course always use `Int` as an index, in the sense that “the value at index `n` is obtained by iterating `n` steps from the start of the sequence”; I’ll assume this doesn’t “count” as an index for purposes of this discussion.</div><div class=""><br class=""></div><div class="">Given the above, I will provide two examples.</div><div class=""><br class=""></div><div class="">Here is one that is stable, re-iterable, infinite, and has no “non-trivial" index:</div><div class=""><br class=""></div><div class=""><div class=""> // Modest generalization of a seedable PRNG.</div><div class=""> // We assume that identically-seeded sources generate</div><div class=""> // identical elements (via `randomElement`), in identical order.</div><div class=""> protocol RandomElementSourceType {</div><div class=""><br class=""></div><div class=""> typealias Element</div><div class=""> typealias Seed: Equatable</div><div class=""> // ^ `:Equatable` isn't actually necessary, but it's nice</div><div class=""> </div><div class=""> init(seed: Seed)</div><div class=""> </div><div class=""> mutating func randomElement() -> Element</div><div class=""><br class=""></div><div class=""> }</div><div class=""><br class=""></div><div class=""> struct RandomElementGenerator<R:RandomElementSourceType> : GeneratorType {</div><div class=""><br class=""></div><div class=""> typealias Element = R.Element</div><div class=""> </div><div class=""> private var source: R</div><div class=""> </div><div class=""> mutating func next() -> Element? {</div><div class=""> return source.randomElement() // <- never stops!</div><div class=""> }</div><div class=""> </div><div class=""> }</div><div class=""><br class=""></div><div class=""> struct RandomElementSequence<R:RandomElementSourceType> : SequenceType {</div><div class=""><br class=""></div><div class=""> typealias Generator = RandomElementGenerator<R></div><div class=""> </div><div class=""> private let seed: R.Seed</div><div class=""> </div><div class=""> func generate() -> Generator {</div><div class=""> return Generator(source: R(seed: seed))</div><div class=""> // ^ as per assumptions, each iteration will be identical b/c</div><div class=""> // because each iteration uses the same seed </div><div class=""> }</div><div class=""><br class=""></div><div class=""> }</div><div class=""><br class=""></div><div class="">…and here is one that is not-necessarily-stable, reiteration-capable, finite (one hopes!), and with no “non-trivial” index:</div><div class=""><br class=""></div><div class=""><div class=""> struct SuperviewGenerator : GeneratorType {</div><div class=""> </div><div class=""> typealias Element = UIView</div><div class=""> </div><div class=""> private var currentView: UIView? // or NSView on OS X, etc.</div><div class=""> </div><div class=""> private init(initialView: UIView?) {</div><div class=""> currentView = initialView</div><div class=""> }</div><div class=""> </div><div class=""> mutating func next() -> Element? {</div><div class=""> guard let here = currentView else {</div><div class=""> return nil</div><div class=""> }</div><div class=""> currentView = here.superview</div><div class=""> return here</div><div class=""> }</div><div class=""> </div><div class=""> }</div><div class=""><br class=""></div><div class=""> // also e.g. analogous constructs for `CALayer`,</div><div class=""> // `UIViewController`, `UIResponder`, “folders/directories”, and so on...</div><div class=""> struct SuperviewSequence : SequenceType {</div><div class=""><br class=""></div><div class=""> typealias Generator = SuperviewGenerator</div><div class=""> </div><div class=""> private let initialView: UIView?</div><div class=""> </div><div class=""> init(initialView: UIView?) {</div><div class=""> self.initialView = initialView</div><div class=""> }</div><div class=""> </div><div class=""> func generate() -> Generator {</div><div class=""> return Generator(initialView: initialView)</div><div class=""> }</div><div class=""> </div><div class=""> func underestimateCount() -> Int {</div><div class=""> return initialView != nil ? 1 : 0</div><div class=""> }</div><div class=""> </div><div class=""> }</div><div class=""> </div><div class=""> // Useful extensions:</div><div class=""> extension UIView {</div><div class=""> </div><div class=""> // Enumerates the view hierarchy upward from `self`, including `self`.</div><div class=""> func inclusiveSuperviewSequence() -> SuperviewSequence {</div><div class=""> return SuperviewSequence(initialView: self)</div><div class=""> }</div><div class=""> </div><div class=""> // Enumerates the view hierarchy upward from `self`, omitting `self`.</div><div class=""> func exclusiveSuperviewSequence() -> SuperviewSequence { </div><div class=""> return SuperviewSequence(initialView: self.superview)</div><div class=""> }</div><div class=""> </div><div class=""> }</div></div></div></div></div></blockquote><br class=""></div><div>I've been musing over these for a few days, and I think the answers are that RandomElementSequence would be a Generator and SuperviewSequence would be a Collection.</div><div><br class=""></div><div><b class="">RandomElementSequence</b>: As you say, this type is copyable, but its iteration is destructive: you can't get back to a previous state via any sort of Index. But that's not a distinction between Sequence and Generator today; there are some Generators that are perfectly copyable and others that are not. (Ideally, the ones that aren't would be made into classes.) If all you have is a generic Generator, you can only iterate it once…but the same is true of Sequence. Knowing the concrete type </div><div><br class=""></div><div>Sure, you could come up with a new protocol, MultipassSequence, but you could just as easily have a MultipassGenerator that just means "this generator is safe to copy". (That's basically <a href="http://en.cppreference.com/w/cpp/iterator" class="">InputIterator vs. ForwardIterator</a> in C++.)</div><div><br class=""></div><div>(Another direction to take this: a degenerate case of an index would be "the entire state of the underlying RNG", but that's not always possible with, say, access control.)</div><div><br class=""></div><div><b class="">SuperviewSequence</b>: Right, so, I claim this is a Collection. Here's my index:</div><div><br class=""></div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><div>public struct SuperviewIndex: ForwardIndexType {</div><div> var currentNode: AnyClass?</div><div><br class=""></div><div> func successor() -> SuperviewIndex {</div><div> guard let currentNode = self.currentNode else {</div><div> fatalError("advanced past the end SuperviewIndex")</div><div> }</div><div> return SuperviewIndex(currentNode.superclass)</div><div> }</div><div>}</div></blockquote><div class=""><br class=""></div>and the CollectionType implementation:<div class=""><br class=""></div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><div class="">public var startIndex: SuperviewIndex { return .init(startNode) }</div><div class="">public var endIndex: SuperviewIndex { return .init(nil) }</div><div class=""><br class=""></div></blockquote><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><div class="">public subscript(index: SuperviewIndex) {</div><div> guard let currentNode = index.currentNode else {</div><div> fatalError("accessed endIndex")</div><div> }</div><div> // Debug-only assertion</div><div> assert(self.indices.contains(index), "not part of this superclass hierarchy")</div><div> return currentNode</div><div class="">}</div></blockquote><div class=""><br class=""></div>It is a little weird that the subscript doesn't depend on 'self' at all, but that's just the nature of the collection: if you want an O(1) access, you're not going through the collection at all. (Try to implement a linked list that conforms to CollectionType using a class and you'll see the same thing. Implement one using an enum and it's even weirder.)<div class=""><br class=""></div><div class=""><br class=""></div><div class="">I'm still trying to come up with a good response to Erica's idea that GeneratorType and CollectionType don't inherently have anything in common, but the gist of it is that there are useful operations common to both kinds of values, which suggests the existence of a more general abstraction. That is, there are things that are obviously Collections and things that are obviously not Collections but could still be Generators, and there are operations (currently on SequenceType) that apply to both.<br class=""><div class=""><br class=""></div><div class="">Jordan<br class=""><div class=""><div><br class=""></div></div></div></div></body></html>