>> 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@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@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
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution
