<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 Jun 22, 2016, at 5:41 PM, Dave Abrahams 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=""><blockquote type="cite" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: 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 agree, names are not the primary issue. <br class=""><br class="">Another issue is that you cannot currently write generic code that<br class="">might need to iterate a sequence more than once. You currently have<br class="">to over-constrain types to `Collection` even if you don’t need to do<br class="">anything other than iterate the elements (the discussion about whether<br class="">`LazyFilterSequnce` has a bug in its `underestimateCount` is relevant<br class="">here).<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: 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-caps: 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="">That's not an over-constraint. Multi-pass-ness *is* the fundamental</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: 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-caps: 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="">distinction between Sequence and Collection. AFAIK there's no multipass</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: 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-caps: 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="">sequence that cannot support indices.</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: 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=""></div></div></blockquote></div><br class=""><div class="">Just wanted to communicate more around this point specifically. If Collections can be infinite (probably adding special meaning to count returning Collection.IndexDistance.max), then the only difference between Sequence and Collection is the indexes. </div><div class=""><br class=""></div><div class="">However, I’m concerned about the delta between an iterator and a full collection. For an example:</div><div class=""><br class=""></div><div class=""><div style="margin: 0px; line-height: normal; font-family: Menlo; font-size: 11px;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #0433ff" class="">class</span><span style="font-variant-ligatures: no-common-ligatures" class=""> FibIterator : </span><span style="font-variant-ligatures: no-common-ligatures; color: #3495af" class="">IteratorProtocol</span><span style="font-variant-ligatures: no-common-ligatures" class=""> {</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; font-size: 11px;" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #0433ff" class="">var</span><span style="font-variant-ligatures: no-common-ligatures" class=""> last = 0, current = 1</span></div><p style="margin: 0px; line-height: normal; font-family: Menlo; min-height: 16px; font-size: 11px;" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><br class="webkit-block-placeholder"></p><div style="margin: 0px; line-height: normal; font-family: Menlo; font-size: 11px;" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #0433ff" class="">func</span><span style="font-variant-ligatures: no-common-ligatures" class=""> next() -> </span><span style="font-variant-ligatures: no-common-ligatures; color: #3495af" class="">Int</span><span style="font-variant-ligatures: no-common-ligatures" class="">? {</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; color: rgb(52, 149, 175); font-size: 11px;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> (</span><span style="font-variant-ligatures: no-common-ligatures" class="">last</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">, </span><span style="font-variant-ligatures: no-common-ligatures" class="">current</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">) = (</span><span style="font-variant-ligatures: no-common-ligatures" class="">current</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">, </span><span style="font-variant-ligatures: no-common-ligatures" class="">current</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> + </span><span style="font-variant-ligatures: no-common-ligatures" class="">last</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">)</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; color: rgb(52, 149, 175); font-size: 11px;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #0433ff" class="">return</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> </span><span style="font-variant-ligatures: no-common-ligatures" class="">current</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; font-size: 11px;" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> }</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; font-size: 11px;" class=""><span style="font-variant-ligatures: no-common-ligatures" class="">}</span></div></div><div style="margin: 0px; line-height: normal; font-family: Menlo; font-size: 11px;" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""><br class=""></span></div><div class="">If subscript indexing on collections isn't required to be an O(1) operation, I don’t see a reason for Sequence to exist - we can simply enumerate the sequence with a numeric index, and iterate up to that count to resolve. But this makes things surprising for those implementing generic algorithms across Collections.</div><div class=""><br class=""></div><div class="">I don’t see a way to get an O(1) integer index and meet all the efficiency constraints of Collection without either memoization or additional complexity on implementing <span style="font-family: Menlo; font-size: 11px;" class="">FibIterator</span>. </div><div class=""><br class=""></div><div class="">1. we could use integer indexes and use a non-recursive technique for calculating the fibonacci value at the specified index. <span class=""><font face="Menlo" class=""><span style="font-size: 11px;" class="">FibIterator basically is rewritten into a function “fibonacci(at index:Int)”. </span></font></span></div><span class=""><div class=""><br class=""></div></span><div class="">2. We could use a copy of <span style="font-family: Menlo; font-size: 11px;" class="">FibIterator</span> as the index, since it is a value type. <span style="font-family: Menlo; font-size: 11px;" class="">FibIterator</span> would need to implement Comparable.</div><div class=""><br class=""></div><div class=""><span class="Apple-tab-span" style="white-space:pre"> </span>2a. We make the index InfiniteSequenceIndex< <span style="font-family: Menlo; font-size: 11px;" class="">FibIterator</span> >, where the wrapper is there to define a consistent EndIndex value. </div><div class=""><br class=""></div><div class=""><span class="Apple-tab-span" style="white-space:pre"> </span>However, Collection’s index(_:offsetBy) allows for negative offsets, which would not be accomplished in O(n).</div><div class=""><br class=""></div><div class=""><span class="Apple-tab-span" style="white-space:pre"> </span>2b. If <span style="font-family: Menlo; font-size: 11px;" class="">FibIterator</span> gains an extra method to become bidirectional we can support index(_:offsetBy) in O(n) time. Note that you would probably want to have a bidirectional iterator define its own endIndex.</div><div class=""><br class=""></div><div class="">-DW</div></body></html>