Opened proposal on Swift-evolution as 0066-binary-search

[lorenzoracca]

Good news guys, I just opened a pull request to swift-evolution and presented the proposal. You can find the pull here!

Hope it will get accepted. Stay tuned on the email discussion and the pull in case we get any news!

Thank you all for your support.

[j-haj]

@lorenzoracca @natecook1000 I'm pasting in Dave's comments below. I'm going to be out of commission the next couple of weeks, FYI. Nate, I agree with your response to Dave.

---

I am posting this review on behalf of Dmitri Gribenko, Max Moiseev, and myself.

on Tue May 03 2016, Chris Lattner swift-evolution@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.

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

[natecook1000]

Thanks, @j-haj! Reading the writing on the wall, I stripped our proposal down a bit—WIP here, if anyone would like to give feedback I can revise and then add it to this repo: https://gist.github.com/natecook1000/c772bd218ac133d26c74cdcdf8b91bda

[natecook1000]

Welp: https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160509/017322.html

[j-haj]

Well it was a good first effort. The rejection is just for the specific proposal right? I assume we can fix, cleanup, and resubmit a new proposal

[lorenzoracca]

Yes I think so. Are we going to continue the project on your gis

[lorenzoracca]

Sorry I had faulty internet connection. Anyway, are we going to continue the project on your gist @natecook1000 or use the current repo? That way we could all contribute.

[j-haj]

I'm fine with whatever. I think Nate may have created the gist to do a quick revision prior to them not accepting the proposal.

[natecook1000]

Right, just wanted to put something up where everyone could see it. I've added the proposal in PR #13.

[natecook1000]

If there aren't any comments, should we submit this? Don't know exactly how the Swift 3 announcement affects things like this, so ¯(ツ)/¯

[j-haj]

@natecook1000 part of me thinks the partition(where:) method should be a separate proposal unless it makes use of the standard library sort. I'm on my phone so I can't really get too into the weeds. Additionally, our goal was for binary search, lower bound, and upper bound - it seems to me anything outside of these should be a separate proposal. That being said, I think it's a good addition to the standard. After the review we got on the last proposal I get the sense they don't want us thinking too outside the box.

[lorenzoracca]

I partly think it the way Jeff thinks. But although we were bound to create binarySearch and upper and lowerBound, I think partition(where:) works great, for you can only use one func to do both things. But it is also right that they don't want us to think out of the box, and it's clear standing on what they said in the review.

Our proposal did go a little far from the original classic-C++-like implementation and went for a much newer (IMHO, better) and synthetic option. They did not like that, peace, unfortunately it is what they approve that should be added to the library.

That said, I'd still want binary search algos to be added to Swift. That was the primary and ultimate reason we all started this. So I suggest we go back to the old project with at least a binarySearch and some surrogate of lower-upperBound. Ultimately that's my opinion on what they think we should do, so it might be very wrong and if you don't agree please share and I'm welcome to change! Their cryptic messages did not help very much, I have to say.

What's obvious is that I'd love to see this reformed implementation, but it has also come obvious to me, ironically, that Swift does not like swift changes. What do y'all think?

[natecook1000]

I based the revised proposal on the feedback from the standard library team that @j-haj pasted in above. To me their feedback distilled down to two points:

1. The binary search algorithms that we proposed (sortedIndex(of:) and sortedRange(of:)) should be part of a larger approach to how sorted collections can be handled in Swift. This may involve a SortedCollection protocol or a wrapping SortedCollection type that includes the sorting predicate.
2. The partitioning methods would be good additions to the standard library if they were part of a separate proposal with some changes.

I don't totally agree with point 1, and don't really have the time or energy to work on thinking through a system like that, so I didn't attempt to address those comments at all. That feels like it would fall in the "wait for Swift 4" bucket at this point in any case.

Point 2 sounded a bit like a "revise and resubmit" response to me, so that's what I focused on. I think the proposal addresses all the specific criticisms from the standard library team and is much more focused on just these methods. My only addition is the isPartitioned(where:) method that I'm on the fence about—perhaps it should move to the "alternatives considered" section. Once these are included in the standard library, proposals for point 1 could use them as their starting point.

Jeff, the partition method is a component of many sorting algorithms—most implementations of the intro and quick sorts (including the stdlib's version) call partition multiple times as they recursively sort a collection. The proposal upgrades the existing partition method to be more general, since the unary predicate provides more flexibility than the existing binary predicate.

[natecook1000]

Hmmm, the way I wrote their point 1 isn't quite right—they didn't necessarily want our specific binary search methods as part of the larger approach. Instead, they wanted any APIs that presented an interface to sorted elements of a collection to be part of a larger approach.

[natecook1000]

I think I'm jumping the gun talking about submitting the proposal—sorry about that! The next step would be to send some version of this to the swift-evo list.

Also, here's the documentation for Python's bisect, which they mentioned in their response. It's approach has some interesting differences compared to C++. (And they called their sorted insertion method "insort", which is super silly.)

[lorenzoracca]

@natecook1000 Thank you for the good work Nate, and sorry for the huge delay. After working on it I think that what the proposal is now fully reflects the feedback of the team, and I like how things got sorted out in the end. I am also fine with keeping isPartitioned(where:) right where it is.

I also checked the bisect funcs in Python and I found them really similar to the result we managed to get in the end, I just really wish we'd found that out earlier. Anyway, Python still keeps the right or left distinction, as in lowerBound and upperBound, while I believe that by putting both of them into the same function and letting the user choose which element to retrieve (whether the upper or lower bound) with a unary predicate is much more efficient and simpler to use as well.

IMO, we're good to go. I'm set to propose, I'll wait for further feedback though.

[j-haj]

@natecook1000 This looks great - awesome work on this. I'm good to submit as well

[nigi66]

@j-haj Hi jeffrey. I sent you a request on your LinkedIn page. please check it. I could not find any email address from you. this is my email address could you please contact me. "saeednezhad@gmail.com" . i would like to talk about your Bachelor Thesis "Determination of Transverse Rotational Axis of Multi-joint Robotic Arm: Application to Computed Tomography". regards, Nazila