> 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++? -Joe > > * The polarity of the predicates is wrong: a method with a “where: > predicate” should always return you the index of an element that > *does* satisfy the predicate. > > * Any code in the proposal should be updated to: > > - conform to the new > indexing model; it still shows indices being moved without > participation of the collection instance. > > - attach the @noescape attribute to a parameter's type, rather than > its name. > > * The existing partition algorithms in the stdlib are indeed hobbled. > The more-general partition function is a great idea, but it belongs in > a separate proposal. > > * Something like the method the proposal calls `partitionedIndex` > *should* be included in the standard library for Swift 3, with the > following differences: > > - it should be called partitionPoint(where:) > > - the meaning of the predicate result should be inverted so that the > result of calling the function points to an element actually > satisfying the predicate > > This would give people the primitive they need to build higher-level > functionality without broadening the interface too far, or committing > us to a design that will be hard to use correctly. > >> * Is the problem being addressed significant enough to warrant a >> change to Swift? > > Yes. > >> * Does this proposal fit well with the feel and direction of Swift? > > Not as written, we think. > >> * If you have used other languages or libraries with a similar >> feature, how do you feel that this proposal compares to those? > > We have used the C++ standard library and Python's `bisect` function. > This proposal is obviously inspired by much of the work in C++, but we > think we can do much better for Swift. > >> * How much effort did you put into your review? A glance, a >> quick reading, or an in-depth study? > > An in-depth study. > >> More information about the Swift evolution process is available at >> >> https://github.com/apple/swift-evolution/blob/master/process.md >> >> Thank you, >> >> -Chris Lattner >> Review Manager >> >> _______________________________________________ >> swift-evolution mailing list >> swift-evolution@swift.org >> https://lists.swift.org/mailman/listinfo/swift-evolution > > Thanks, > > -- > Dave > > _______________________________________________ > swift-evolution mailing list > swift-evolution@swift.org > https://lists.swift.org/mailman/listinfo/swift-evolution _______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution