on Tue May 10 2016, Joe Groff <swift-evolution@swift.org> wrote: >> On May 6, 2016, at 3:16 PM, Dave Abrahams via swift-evolution >> <swift-evolution@swift.org> wrote: >> >> >> I am posting this review on behalf of Dmitri Gribenko, Max Moiseev, and >> myself. > >> >> on Tue May 03 2016, Chris Lattner <swift-evolution@swift.org> wrote: >> >>> Hello Swift community, >>> >>> The review of "SE-0074: Implementation of Binary Search functions" >>> begins now and runs through May 9. The proposal is available here: >>> >>> >>> https://github.com/apple/swift-evolution/blob/master/proposals/0074-binary-search.md >>> >>> Reviews are an important part of the Swift evolution process. All >>> reviews should be sent to the swift-evolution mailing list at >>> >>> https://lists.swift.org/mailman/listinfo/swift-evolution >>> >>> or, if you would like to keep your feedback private, directly to the review >>> manager. >>> >>> What goes into a review? >>> >>> The goal of the review process is to improve the proposal under review >>> through constructive criticism and contribute to the direction of >>> Swift. When writing your review, here are some questions you might >>> want to answer in your review: >>> >>> * What is your evaluation of the proposal? >> >> We think binary searches are fundamental and important, and want to see >> them added. However, we don't agree with the form of the current >> proposal. In particular, we think: >> >> * Operations that depend on sorted-ness and use binary predicates should >> not be available on all Collections; they're too easy to misuse, >> they're hard to name well, and as Nicola Salmoria has noted, they >> would not make any sense at all for a Set<T>. >> >> * They should be scoped to a kind of collection that bundles >> the predicate with the elements, e.g. >> >> let x = Sorted([3, 4, 1, 5, 2], >) // stores a sorted copy of >> the array >> let y = Sorted(preSorted: 0..<100, <) // stores a copy of the range >> >> Maybe there should also be protocols for this; CountableRange<T> would >> already already conform to the immutable version. We might want a >> mutable form of the protocol for sorted collections with >> insertion/removal methods. This whole area needs more design. > > I worry that attaching these methods to a strongly-typed `Sorted` > wrapper limits their appeal. It's useful to be able to binary-search > through data in a standard container that's known to be sorted, or > over a subregion of the data that's sorted. While you can of course > cobble together a Sorted(Slice(container[sortedRange])), that's pretty > inconvenient. Is misapplying binary search algorithms to unsorted data > a big problem in practice in C++?
No, but: 1. Algorithms on collections in C++ are not methods that you'd find by code completion. 2. We have stronger naming conventions than C++ does, such that we're inclined to stick the word “sorted” into the names of all the algorithms that have a sortedness precondition. There are a few of them; e.g. don't forget unique(). The resulting design gets pretty ugly. 3. The idea of a collection that maintains its sorted order is a powerful one that has been useful in practice -- -Dave _______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution