<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 11:37 AM, Jordan Rose via swift-evolution &lt;<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>&gt; 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&nbsp;<i class="">operations</i>&nbsp;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><br class=""></div><div>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><br class=""></div><div>- can be re-iterated (thus not a `Generator`)</div><div>- has no meaningful index (!) (thus not a `Collection`)</div><div><br class=""></div><div>…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><br class=""></div><div>Given the above, I will provide two examples.</div><div><br class=""></div><div>Here is one that is stable, re-iterable, infinite, and has no “non-trivial" index:</div><div><br class=""></div><div><div>&nbsp; &nbsp; // Modest generalization of a seedable PRNG.</div><div>&nbsp; &nbsp; // We assume that identically-seeded sources generate</div><div>&nbsp; &nbsp; // identical elements (via `randomElement`), in identical order.</div><div>&nbsp; &nbsp; protocol RandomElementSourceType {</div><div><br class=""></div><div>&nbsp; &nbsp; &nbsp; typealias Element</div><div>&nbsp; &nbsp; &nbsp; typealias Seed: Equatable</div><div>&nbsp; &nbsp; &nbsp; // ^ `:Equatable` isn't actually necessary, but it's nice</div><div>&nbsp;&nbsp;</div><div>&nbsp; &nbsp; &nbsp; init(seed: Seed)</div><div>&nbsp;&nbsp;</div><div>&nbsp; &nbsp; &nbsp; mutating func randomElement() -&gt; Element</div><div><br class=""></div><div>&nbsp; &nbsp; }</div><div><br class=""></div><div>&nbsp; &nbsp; struct RandomElementGenerator&lt;R:RandomElementSourceType&gt; : GeneratorType {</div><div><br class=""></div><div>&nbsp; &nbsp; &nbsp; typealias Element = R.Element</div><div>&nbsp;&nbsp;</div><div>&nbsp; &nbsp; &nbsp; private var source: R</div><div>&nbsp;&nbsp;</div><div>&nbsp; &nbsp; &nbsp; mutating func next() -&gt; Element? {</div><div>&nbsp; &nbsp; &nbsp; &nbsp; return source.randomElement() // &lt;- never stops!</div><div>&nbsp; &nbsp; &nbsp; }</div><div>&nbsp;&nbsp;</div><div>&nbsp; &nbsp; }</div><div><br class=""></div><div>&nbsp; &nbsp; struct RandomElementSequence&lt;R:RandomElementSourceType&gt; : SequenceType {</div><div><br class=""></div><div>&nbsp; &nbsp; &nbsp; typealias Generator = RandomElementGenerator&lt;R&gt;</div><div>&nbsp;&nbsp;</div><div>&nbsp; &nbsp; &nbsp; private let seed: R.Seed</div><div>&nbsp;&nbsp;</div><div>&nbsp; &nbsp; &nbsp; func generate() -&gt; Generator {</div><div>&nbsp; &nbsp; &nbsp; &nbsp; return Generator(source: R(seed: seed))</div><div>&nbsp; &nbsp; &nbsp; &nbsp; // ^ as per assumptions, each iteration will be identical b/c</div><div>&nbsp; &nbsp; &nbsp; &nbsp; // &nbsp; because each iteration uses the same seed&nbsp;</div><div>&nbsp; &nbsp; &nbsp; }</div><div><br class=""></div><div>&nbsp; &nbsp; }</div><div><br class=""></div><div>…and here is one that is not-necessarily-stable, reiteration-capable, finite (one hopes!), and with no “non-trivial” index:</div><div><br class=""></div><div><div>&nbsp; &nbsp; struct SuperviewGenerator : GeneratorType {</div><div>&nbsp; &nbsp;&nbsp;</div><div>&nbsp; &nbsp; &nbsp; typealias Element = UIView</div><div>&nbsp; &nbsp;&nbsp;</div><div>&nbsp; &nbsp; &nbsp; private var currentView: UIView? // or NSView on OS X, etc.</div><div>&nbsp; &nbsp; &nbsp;&nbsp;</div><div>&nbsp; &nbsp; &nbsp; private init(initialView: UIView?) {</div><div>&nbsp; &nbsp; &nbsp; &nbsp; currentView = initialView</div><div>&nbsp; &nbsp; &nbsp; }</div><div>&nbsp; &nbsp; &nbsp;&nbsp;</div><div>&nbsp; &nbsp; &nbsp; mutating func next() -&gt; Element? {</div><div>&nbsp; &nbsp; &nbsp; &nbsp; guard let here = currentView else {</div><div>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return nil</div><div>&nbsp; &nbsp; &nbsp; &nbsp; }</div><div>&nbsp; &nbsp; &nbsp; &nbsp; currentView = here.superview</div><div>&nbsp; &nbsp; &nbsp; &nbsp; return here</div><div>&nbsp; &nbsp; &nbsp; }</div><div>&nbsp; &nbsp;&nbsp;</div><div>&nbsp; &nbsp; }</div><div><br class=""></div><div>&nbsp; &nbsp; // also e.g. analogous constructs for `CALayer`,</div><div>&nbsp; &nbsp; // `UIViewController`, `UIResponder`, “folders/directories”, and so on...</div><div>&nbsp; &nbsp; struct SuperviewSequence : SequenceType {</div><div><br class=""></div><div>&nbsp; &nbsp; &nbsp; typealias Generator = SuperviewGenerator</div><div>&nbsp; &nbsp; &nbsp;&nbsp;</div><div>&nbsp; &nbsp; &nbsp; private let initialView: UIView?</div><div>&nbsp; &nbsp; &nbsp;&nbsp;</div><div>&nbsp; &nbsp; &nbsp; init(initialView: UIView?) {</div><div>&nbsp; &nbsp; &nbsp; &nbsp; self.initialView = initialView</div><div>&nbsp; &nbsp; &nbsp; }</div><div>&nbsp; &nbsp; &nbsp;&nbsp;</div><div>&nbsp; &nbsp; &nbsp; func generate() -&gt; Generator {</div><div>&nbsp; &nbsp; &nbsp; &nbsp; return Generator(initialView: initialView)</div><div>&nbsp; &nbsp; &nbsp; }</div><div>&nbsp; &nbsp; &nbsp;&nbsp;</div><div>&nbsp; &nbsp; &nbsp; func underestimateCount() -&gt; Int {</div><div>&nbsp; &nbsp; &nbsp; &nbsp; return initialView != nil ? 1 : 0</div><div>&nbsp; &nbsp; &nbsp; }</div><div>&nbsp; &nbsp; &nbsp;&nbsp;</div><div>&nbsp; &nbsp; }</div><div>&nbsp; &nbsp;&nbsp;</div><div>&nbsp; &nbsp; // Useful extensions:</div><div>&nbsp; &nbsp; extension UIView {</div><div>&nbsp; &nbsp;&nbsp;</div><div>&nbsp; &nbsp; &nbsp; // Enumerates the view hierarchy upward from `self`, including `self`.</div><div>&nbsp; &nbsp; &nbsp; func inclusiveSuperviewSequence() -&gt; SuperviewSequence {</div><div>&nbsp; &nbsp; &nbsp; &nbsp; return SuperviewSequence(initialView: self)</div><div>&nbsp; &nbsp; &nbsp; }</div><div>&nbsp; &nbsp; &nbsp;&nbsp;</div><div>&nbsp; &nbsp; &nbsp; // Enumerates the view hierarchy upward from `self`, omitting `self`.</div><div>&nbsp; &nbsp; &nbsp; func exclusiveSuperviewSequence() -&gt; SuperviewSequence {&nbsp;</div><div>&nbsp; &nbsp; &nbsp; &nbsp; return SuperviewSequence(initialView: self.superview)</div><div>&nbsp; &nbsp; &nbsp; }</div><div>&nbsp; &nbsp;&nbsp;</div><div>&nbsp; &nbsp; }</div><div><br class=""></div><div><br class=""></div></div><div class=""><br class=""></div></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><br class=""><div class=""><blockquote type="cite" class=""><div class="">On Dec 31, 2015, at 9:52, Erica Sadun via swift-evolution &lt;<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>&gt; wrote:</div><br class="Apple-interchange-newline"><div class=""><div class="">I'm trying to work them out, so it's still muddled.</div><div class=""><br class=""></div><div class="">Right now, I think&nbsp;<font face="Menlo" class="">SequenceType</font>&nbsp;is better described as&nbsp;<font face="Menlo" class="">CollectionWalkType</font>&nbsp;but that's kind of (1) a mouthful and (2) not entirely accurate.&nbsp;</div><div class=""><br class=""></div><div class="">Moving back a step:&nbsp;<font face="Menlo" class="">SequenceType</font>&nbsp;is defined as: "A type that can be iterated with a `for`...`in` loop." But it says nothing about whether that loop ever terminates and many stdlib sequence functions currently don't make sense (at least if they're not lazy) with respect to infinite sequences, which should probably be "<font face="Menlo" class="">StreamType</font>" not sequences. A couple of examples:</div><div class=""><ul class=""><li class="">Here's my fib:&nbsp;<a href="http://swiftstub.com/189513594/" class="">http://swiftstub.com/189513594/</a></li><li class="">And here's Oisin's user-input sequence: &nbsp;<a href="https://gist.github.com/oisdk/2c7ac33bf2188528842a" class="">https://gist.github.com/oisdk/2c7ac33bf2188528842a</a></li></ul></div><div class="">Both of these are theoretically filterable, but they aren't dropLast-able, suffix-able, properly split-able, etc.</div><div class=""><br class=""></div><div class="">Hopefully that's enough of a starting point to indicate where my thinking is at and what I'm trying to think through when it comes to this. -- E</div><div class=""><br class=""></div><br class=""><div class=""><blockquote type="cite" class=""><div class="">On Dec 31, 2015, at 10:09 AM, Dave Abrahams &lt;<a href="mailto:dabrahams@apple.com" class="">dabrahams@apple.com</a>&gt; wrote:</div><br class="Apple-interchange-newline"><div class=""><div class=""><br class=""><blockquote type="cite" class="">On Dec 31, 2015, at 9:05 AM, Erica Sadun via swift-evolution &lt;<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>&gt; wrote:<br class=""><br class="">It does seem that in Swift the concepts of collection, sequence, permutation, stream, etc are a bit muddled.<br class=""></blockquote><br class="">This is a pretty vague critique. &nbsp;Do you have specifics, and suggestions that address them?<br class=""><br class=""><blockquote type="cite" class=""><br class="">-- E<br class=""><br class=""><br class=""><blockquote type="cite" class="">On Dec 31, 2015, at 6:51 AM, Tino Heth via swift-evolution &lt;<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>&gt; wrote:<br class=""><br class=""><blockquote type="cite" class="">Those are collections. &nbsp;Collections can be iterated over multiple times.<br class=""></blockquote>Speaking of the Fibonacci-numbers:<br class="">Sure we can write an algorithm that iterates over them several times — it just won't ever finish the first iteration ;-)<br class="">(only nitpicking — I just couldn't resist)<br class=""><br class="">Happy new year!<br class="">_______________________________________________<br class="">swift-evolution mailing list<br class=""><a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a><br class=""><a href="https://lists.swift.org/mailman/listinfo/swift-evolution" class="">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br class=""></blockquote><br class="">_______________________________________________<br class="">swift-evolution mailing list<br class=""><a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a><br class=""><a href="https://lists.swift.org/mailman/listinfo/swift-evolution" class="">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br class=""></blockquote><br class="">-Dave<br class=""><br class=""></div></div></blockquote></div><br class=""><span id="cid:CB35B16C-4004-4CCD-B338-F41B396501AD@localhost">&lt;open.gif&gt;</span><span class="" style="float: none; display: inline !important;">&nbsp;</span><span class="" style="float: none; display: inline !important;">_______________________________________________</span><br class=""><span class="" style="float: none; display: inline !important;">swift-evolution mailing list</span><br class=""><a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a><br class=""><a href="https://lists.swift.org/mailman/listinfo/swift-evolution" class="">https://lists.swift.org/mailman/listinfo/swift-evolution</a></div></blockquote><div class=""><br class=""></div></div></div><img src="https://u2002410.ct.sendgrid.net/wf/open?upn=9EwXyNl81W9TT3yZ17PL28-2Be7Ks-2FXLjqa0dZcsddi5ZDOQryJvq5K9Z81NEHCRMS3YebeHa7L21Sufeu9SxPFnnSCbr5qoVznaDTXvrt3ItuSM2AEjSw7kuTF3VKZTURiuKmijTGtTfN8GrP6j3bHLi0cSOwtkgQMZBXKfRb-2FhgPZGTzCcsitrIDrT4SQt6RlHFzQoTaM3SkBsdX9JmCxJpjKWHoJPts9FnW6ZunT0E-3D" alt="" width="1" height="1" border="0" 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; height: 1px !important; width: 1px !important; border-width: 0px !important; margin: 0px !important; padding: 0px !important;" class=""><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=""><span class="Apple-converted-space">&nbsp;</span>_______________________________________________</span><br 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=""><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="">swift-evolution mailing list</span><br 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=""><a href="mailto:swift-evolution@swift.org" 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="">swift-evolution@swift.org</a><br 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=""><a href="https://lists.swift.org/mailman/listinfo/swift-evolution" 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="">https://lists.swift.org/mailman/listinfo/swift-evolution</a></div></blockquote></div><br class=""></body></html>