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. * 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