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

[Dave Abrahams]

on Tue May 10 2016, Joe Groff <swift-evolution at swift.org> wrote:

>> 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++?

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