<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=""><div><blockquote type="cite" class=""><blockquote type="cite" class="">Proposal:</blockquote></blockquote><blockquote type="cite" class=""><blockquote type="cite" class=""><br class=""></blockquote></blockquote><blockquote type="cite" class=""><div class=""><blockquote type="cite" class=""><span class="Apple-tab-span" style="white-space: pre;"> </span><a href="https://github.com/apple/swift-evolution/blob/master/proposals/0074-binary-search.md" class="">https://github.com/apple/swift-evolution/blob/master/proposals/0074-binary-search.md</a></blockquote></div></blockquote><div><br class=""></div><blockquote type="cite" class=""><div class="">On May 6, 2016, at 5:16 PM, Dave Abrahams via swift-evolution <<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>> wrote:</div><div class=""><div class=""><br class="">I am posting this review on behalf of Dmitri Gribenko, Max Moiseev, and<br class="">myself.<br class=""></div></div></blockquote><div><br class=""></div><div>Thanks for the feedback! This reply is only from me—I haven't had a chance to consult with the other authors and they may disagree with me or have better arguments on everything below. </div><br class=""><blockquote type="cite" class=""><div class=""><div class=""><blockquote type="cite" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>* What is your evaluation of the proposal?<br class=""></blockquote><br class="">We think binary searches are fundamental and important, and want to see<br class="">them added. However, we don't agree with the form of the current<br class="">proposal. In particular, we think:<br class=""><br 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=""></div></div></blockquote><div><blockquote type="cite" class=""><br class=""></blockquote></div><blockquote type="cite" class=""><div class=""><div 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=""></div></div></blockquote><div><br class=""></div><div>I can certainly see this as an alternate approach. I would still prefer to have access to APIs that require but don't enforce sorting as a precondition, since, as Brent mentioned, sorted arrays are fairly common. That said, if there's a thoughtfully designed collection protocol and a "sorted collection" wrapper that doe smart things without duplicating storage, I'd be on board with that as well.</div><div><div><br class=""></div></div><blockquote type="cite" class=""><div class=""><div class="">* The polarity of the predicates is wrong: a method with a “where:<br class=""> predicate” should always return you the index of an element that<br class=""> *does* satisfy the predicate.<br class=""></div></div></blockquote><div><br class=""></div><div>Wow, yeah, this is totally backwards. So these should really be: </div><div><br class=""></div></div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><div><div><font face="Menlo" class="">let a = [10, 20, 30, 30, 30, 40, 60]</font></div><div><font face="Menlo" class="">a.partitionedIndex(where: { $0 >= 20 }) // 1</font></div><div><font face="Menlo" class=""><br class=""></font></div><div><font face="Menlo" class="">let lowerBound30 = </font><span style="font-family: Menlo;" class="">a.partitionedIndex</span><font face="Menlo" class="">(where: { $0 >= 30 })</font></div><div><font face="Menlo" class="">let upperBound30 = </font><span style="font-family: Menlo;" class="">a.partitionedIndex</span><font face="Menlo" class="">(where: { $0 > 30 })</font></div></div></blockquote><div><br class=""></div><div><blockquote type="cite" class=""><div class=""><div class="">* Any code in the proposal should be updated to:<br class=""><br class=""> - conform to the new<br class=""> indexing model; it still shows indices being moved without<br class=""> participation of the collection instance.<br class=""><br class=""> - attach the @noescape attribute to a parameter's type, rather than <br class=""> its name.<br class=""><br class="">* The existing partition algorithms in the stdlib are indeed hobbled.<br class=""> The more-general partition function is a great idea, but it belongs in<br class=""> a separate proposal.<br class=""><br class="">* Something like the method the proposal calls `partitionedIndex`<br class=""> *should* be included in the standard library for Swift 3, with the<br class=""> following differences:<br class=""><br class=""> - it should be called partitionPoint(where:)<br class=""><br class=""> - the meaning of the predicate result should be inverted so that the<br class=""> result of calling the function points to an element actually<br class=""> satisfying the predicate<br class=""><br class=""> This would give people the primitive they need to build higher-level<br class=""> functionality without broadening the interface too far, or committing<br class=""> us to a design that will be hard to use correctly.<br class=""></div></div></blockquote><div><br class=""></div><div>This would definitely be a more limited and focused proposal. Thanks again for the feedback!</div><div><br class=""></div><div>Nate</div><div><br class=""></div><blockquote type="cite" class=""><div class=""><div class=""><blockquote type="cite" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>* Is the problem being addressed significant enough to warrant a<br class="">change to Swift? <br class=""></blockquote><br class="">Yes.<br class=""><br class=""><blockquote type="cite" class="">* Does this proposal fit well with the feel and direction of Swift? <br class=""></blockquote><br class="">Not as written, we think.<br class=""><br class=""><blockquote type="cite" class="">* If you have used other languages or libraries with a similar<br class="">feature, how do you feel that this proposal compares to those?<br class=""></blockquote><br class="">We have used the C++ standard library and Python's `bisect` function.<br class="">This proposal is obviously inspired by much of the work in C++, but we<br class="">think we can do much better for Swift.<br class=""><br class=""><blockquote type="cite" class="">* How much effort did you put into your review? A glance, a<br class="">quick reading, or an in-depth study?<br class=""></blockquote><br class="">An in-depth study. <br class=""><br class=""><blockquote type="cite" class="">More information about the Swift evolution process is available at<br class=""><br class=""><span class="Apple-tab-span" style="white-space:pre"> </span><a href="https://github.com/apple/swift-evolution/blob/master/process.md" class="">https://github.com/apple/swift-evolution/blob/master/process.md</a><br class=""><br class="">Thank you,<br class=""><br class="">-Chris Lattner<br class="">Review Manager<br class=""><br class="">_______________________________________________<br class="">swift-evolution mailing list<br class="">swift-evolution@swift.org<br class="">https://lists.swift.org/mailman/listinfo/swift-evolution<br class=""></blockquote><br class="">Thanks,<br class=""><br class="">-- <br class="">Dave<br class=""><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="">https://lists.swift.org/mailman/listinfo/swift-evolution<br class=""></div></div></blockquote></div><br class=""></body></html>