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

[Dave Abrahams]

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.

* 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