<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 11, 2016, at 5:21 PM, Jordan Rose <<a href="mailto:jordan_rose@apple.com" class="">jordan_rose@apple.com</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 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 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;"><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 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="">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 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=""><br class=""></div><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=""><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></blockquote><div><br class=""></div><div>^ did something get edited out here?</div><br class=""><blockquote type="cite" class=""><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=""><br class=""></div><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="">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></blockquote><div><br class=""></div><div>I’m almost ready to make a proposal for something along those lines, actually, although these responses mean I’ll be revising it a bit first.</div><br class=""><blockquote type="cite" class=""><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=""><br class=""></div><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="">(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></blockquote><div><br class=""></div><div>Dmitri suggested this also; I don’t see what the natural `endIndex` would be here (that isn’t just, say, created by artificially truncating the underlying sequence).</div><div><br class=""></div><blockquote type="cite" class=""><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=""><b class="">SuperviewSequence</b>: Right, so, I claim this is a Collection. Here's my index:</div><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=""><br class=""></div><blockquote 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; margin: 0px 0px 0px 40px; border: none; padding: 0px;"><div class="">public struct SuperviewIndex: ForwardIndexType {</div><div class=""> var currentNode: AnyClass?</div><div class=""><br class=""></div><div class=""> func successor() -> SuperviewIndex {</div><div class=""> guard let currentNode = self.currentNode else {</div><div class=""> fatalError("advanced past the end SuperviewIndex")</div><div class=""> }</div><div class=""> return SuperviewIndex(currentNode.superclass)</div><div class=""> }</div><div class="">}</div></blockquote><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;"><br class=""></div><span 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; float: none; display: inline !important;" class="">and the CollectionType implementation:</span><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;"><br class=""></div><blockquote 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; margin: 0px 0px 0px 40px; border: none; padding: 0px;"><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 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; margin: 0px 0px 0px 40px; border: none; padding: 0px;"><div class="">public subscript(index: SuperviewIndex) {</div><div class=""> guard let currentNode = index.currentNode else {</div><div class=""> fatalError("accessed endIndex")</div><div class=""> }</div><div class=""> // Debug-only assertion</div><div class=""> assert(self.indices.contains(index), "not part of this superclass hierarchy")</div><div class=""> return currentNode</div><div class="">}</div></blockquote></div></blockquote><div><br class=""></div><div>I have to hand it to you here, it really does meet the requirements; this is a good trick to be aware of. </div><div><br class=""></div><div>Interestingly-enough, I hadn’t actually actually considered writing a superclass sequence, but it’d certainly have its own uses.</div><div><br class=""></div><div>It also highlights that `ForwardIndexType` and `GeneratorType` are suspiciously similar, and would be even more so in a “collections move indices” world (e.g. SR-122, which I hope is adopted in some form).</div><br class=""><blockquote type="cite" class=""><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;"><br class=""></div><span 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; float: none; display: inline !important;" class="">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.)</span></div></blockquote><blockquote type="cite" class=""><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;"><br class=""></div><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;"><br class=""></div><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;">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></div></blockquote><div><br class=""></div><div>FWIW, I’d say that it’s less that theres an actual common abstraction here as that you have a bunch of operations that *could* be defined on `GeneratorType` (though currently are-defined on `SequenceType`), but because you can always get a “canonical” generator from a `CollectionType` it becomes easy to start eliding this distinction…and after awhile you might start referring to these generator-operations as applying to both.</div><div><br class=""></div><div>That’s just one interpretation, though.</div><div><br class=""></div><div>Thanks for the considered response; I’ve picked up a couple tricks and now have some food for thought.</div><div><br class=""></div><blockquote type="cite" class=""><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=""><br class=""></div><div class="">Jordan</div></div></div></blockquote></div><br class=""></body></html>