[swift-evolution] [Review] SE-0074: Implementation of Binary Search functions

[Joe Groff]

> On May 6, 2016, at 3:16 PM, Dave Abrahams via swift-evolution <swift-evolution at 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 at 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 at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
> 
> Thanks,
> 
> -- 
> Dave
> 
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution