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

[Nate Cook]

>> Proposal:
>> 
>> 	https://github.com/apple/swift-evolution/blob/master/proposals/0074-binary-search.md <https://github.com/apple/swift-evolution/blob/master/proposals/0074-binary-search.md>
> On May 6, 2016, at 5: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.

Thanks for the feedback! This reply is only from me—I haven't had a chance to consult with the other authors and they may disagree with me or have better arguments on everything below. 

>> 	* 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 can certainly see this as an alternate approach. I would still prefer to have access to APIs that require but don't enforce sorting as a precondition, since, as Brent mentioned, sorted arrays are fairly common. That said, if there's a thoughtfully designed collection protocol and a "sorted collection" wrapper that doe smart things without duplicating storage, I'd be on board with that as well.

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

Wow, yeah, this is totally backwards. So these should really be: 

let a = [10, 20, 30, 30, 30, 40, 60]
a.partitionedIndex(where: { $0 >= 20 })     // 1

let lowerBound30 = a.partitionedIndex(where: { $0 >= 30 })
let upperBound30 = a.partitionedIndex(where: { $0 > 30 })

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

This would definitely be a more limited and focused proposal. Thanks again for the feedback!

Nate

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160509/9dc00ef4/attachment.html>