<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 May 9, 2016, at 10:28 PM, Nate Cook 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-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=""><blockquote type="cite" class=""><div class="">On May 9, 2016, at 9:48 PM, Joe Groff 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=""><blockquote type="cite" class="" 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;"><br class="Apple-interchange-newline">On May 9, 2016, at 6:23 PM, Brent Royal-Gordon via swift-evolution <<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>> wrote:<br class=""><br class=""><blockquote type="cite" class="">* Operations that depend on sorted-ness and use binary predicates should<br class="">not be available on all Collections; they're too easy to misuse,<br class="">they're hard to name well, and as Nicola Salmoria has noted, they<br class="">would not make any sense at all for a Set<T>.<br class=""><br class="">* They should be scoped to a kind of collection that bundles<br class="">the predicate with the elements, e.g.<br class=""><br class=""> let x = Sorted([3, 4, 1, 5, 2], >) // stores a sorted copy of the array<br class=""> let y = Sorted(preSorted: 0..<100, <) // stores a copy of the range<br class=""><br class="">Maybe there should also be protocols for this; CountableRange<T> would<br class="">already already conform to the immutable version. We might want a<br class="">mutable form of the protocol for sorted collections with<br class="">insertion/removal methods. This whole area needs more design.<br class=""></blockquote><br class="">I agree with both of these statements, but not with your conclusion.<br class=""><br class="">There are three classes of collections:<br class=""><br class="">1) Those which are always sorted, like a SortedSet.<br class="">2) Those which may or may not be sorted, like an Array.<br class="">3) Those which are never sorted, like a Set.<br class=""><br class="">These APIs are useless on a #3, but #2 is still a valuable use case to support. In particular, it's quite common to use sorted `Array`s, and these APIs would help you do that.<br class=""><br class="">What I might consider doing is tying this to `RangeReplaceableCollection`. That protocol is applied only to types which allow insertion at arbitrary indices, which is a good, though not perfect, proxy for types which might allow you to manually maintain a sort order. `Array`, `ArraySlice`, `ContiguousArray`, and the mutable `String` views would get these methods, while `Set` and `Dictionary` would not.<br class=""></blockquote><br class="" 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;"><span class="" 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;">We could also introduce a new OrderedCollection protocol. (This would also be useful in the future for supporting `case` pattern matching on collections. It makes sense to pattern-match arrays and other ordered collections in order by element, but you'd expect very different semantics pattern-matching an unordered Set.)</span><br class="" 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;"></div></blockquote></div></div></blockquote><div><br class=""></div>I have some high-level comments about this proposal: it feels rather muddled and as if it's mixing different concerns.</div><div><br class=""></div><div>Taking a step back, at a *minimum* I think the right way to add this functionality is to:</div><div><br class=""></div><div>A) add generic functions like `binarySearch` (etc.) to `Collection` (taking the GIGO risk, of course)</div><div>B) add overridable methods like `sortedIndex(of:)` to `Collection` (taking the GIGO risk again, of course)</div><div>C) provide default implementations of e.g. `sortedIndex(of:)` that use `binarySearch` (etc.)</div><div><br class=""></div><div>…and *ideally* I think both (A) and probably (B) wind up introducing some methods like `_customBinarySearchForComparableElement` (etc.), but that is a level of detail that can be skipped for this discussion.</div><div><br class=""></div><div>I understand the motivation to try and add only “intent-focused” methods like `sortedIndex(of:)`, but a binary search should be expressible generically and is a very useful building block to have when building such higher-level methods; it would also prove useful to *implement* the `Sorted(…)` concept mentioned above, one would think.</div><div><br class=""></div><div>I also think it will be a mistake to restrict the availability of any of these APIs to “sorted” collections; there are several reasons here. </div><div><br class=""></div><div>One reason is simply b/c such sorted collections aren’t part of the standard library yet. </div><div><br class=""></div><div>Also, it seems like for *some* of these methods (binarySearch) it’s a category error to restrict them to sorted collections: such sorted collections should instead simply exploit their own ordering/structure where appropriate! </div><div><br class=""></div><div>Finally, things like binary searches are often basic building blocks (etc.) for *constructing* such ordered collections, and thus being unable to use them in that context would be limiting (e.g. if you wanted to implement `Sorted(…)` as suggested above, you’d probably benefit from being able to use these methods…).</div><div><br class=""></div><div>Thus although I understand the desire for jumping immediately to the higher-level, "intent-focused” API, and although I understand the GIGO risk for having some of these methods defined too broadly, I am not sure the cures aren't worse than the disease here, so to speak.</div><div><br class=""></div><div><blockquote type="cite" class=""><div class=""><div 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 class=""><blockquote type="cite" class=""><br class=""></blockquote></div><div class=""><blockquote type="cite" class=""><span class="" style="float: none; display: inline !important;">-Joe</span><br class=""></blockquote><br class=""></div><div class="">Yet another alternative would be to drop Set and Dictionary down a level to a FiniteSequence protocol in between Sequence and Collection. Basically none of the index-based collection APIs (i.e. everything except `count` and `isEmpty`) make sense on sets and dictionaries. index(where:) was marginally useful with dictionaries, but now that Sequence is getting first(where:), née find(...), even that isn't necessary.</div></div></div></blockquote><div><br class=""></div><div>I’ve argued this (unsuccessfully) here in the past, but with 2 such distinctions:</div><div><br class=""></div><div>- Sequence -> FiniteSequence </div><div>- Sequence -> StableSequence (“stable” meaning identical on each iteration)</div><div>- Collection: FiniteSequence, StableSequence</div><div><br class=""></div><div>…but it didn’t go well; I can certainly dredge up my design notes if there’s someone else interested in taking up this case.</div><br class=""><blockquote type="cite" class=""><div class=""><div 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 class=""><br class=""></div><div class="">Nate</div><div class=""><br class=""></div></div><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="">_______________________________________________</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="">swift-evolution mailing list</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=""><a href="mailto:swift-evolution@swift.org" 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="">swift-evolution@swift.org</a><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=""><a href="https://lists.swift.org/mailman/listinfo/swift-evolution" 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="">https://lists.swift.org/mailman/listinfo/swift-evolution</a></div></blockquote></div><br class=""></body></html>