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

[Nicola Salmoria]

> * What is your evaluation of the proposal?

I support the idea, since binary search is obviously a very important
algorithm which would be important to have in the standard library.

I am, however, unsure about the implementation. The current proposal
suggests to add the new methods to the Collection protocol, leaving to the
caller the burden of ensuring that the collection is properly sorted, and
giving up on the opportunity of using types to enforce the invariant.

In addition, the whole idea of being sorted doesn't even make sense for many
Collections: e.g. a Dictionary can never be in a condition where calling a
sortedIndex() method would make sense, so it seems odd that the protocol
would allow it.

Another thing to notice is that the isOrderedBefore predicate passed to
sortedIndex() can't be arbitrary, but must be the same predicate used to
sort the collection in the first place. It would therefore seem natural for
the predicate to be part of the collection itself, and not be passed to
sortedIndex().

It seems to me that it would be more appropriate to have new
SortedCollection protocol, declaring the proposed methods. The sorted()
method of Collection would need to return a new type similar to Array but
conforming to the SortedCollection protocol. I'm afraid I don't know how
in-place sort() could be handled efficiently.

Mind you, I'm not sure if such an approach would actually be viable, but the
fact that the "Alternatives considered" section doesn't mention it makes me
think that the authors haven't fully evaluated the possibility.

> * Is the problem being addressed significant enough to warrant a change to
Swift?

Yes, it's important for the standard library to provide common efficient
algorithms.

> * Does this proposal fit well with the feel and direction of Swift?

For the reasons said above, I don't think it fits perfectly. However, if it
isn't possible to do better, this would be at least a first step.

> * If you have used other languages or libraries with a similar feature,
how do you feel that this proposal compares to those?

I've used the C++ counterparts that are referenced in the proposal. Very
recently, I worked on a project where an array violated the prerequisite of
being sorted, causing bugs. So my concerns stated above are very real and I
have personally run into them.

> * How much effort did you put into your review? A glance, a quick reading,
or an in-depth study?

A quick reading and my past experience with this kind of algorithms.

--
Nicola