[swift-evolution] [Proposal] Add Binary Search functions to SequenceType

[Dave Abrahams]

on Tue Mar 15 2016, Nate Cook <swift-evolution at swift.org> wrote:

>> On Mar 15, 2016, at 1:58 PM, Lorenzo Racca via swift-evolution <swift-evolution at swift.org> wrote:
>> 
>>> On Mar 15, 2016, at 6:49 PM, Haravikk
>>> <swift-evolution at haravikk.me
>>> <mailto:swift-evolution at haravikk.me>>
>
>>> wrote:
>>> 
>>>> On 15 Mar 2016, at 15:48, Lorenzo Racca <lorenzo.racca at live.it <mailto:lorenzo.racca at live.it>> wrote:
>>>> 
>>>> I already knew the impossibility of applying such a predicate as “$0 == 3” and I actually couldn’t quite figure out a solution.
>>> 
>>> I thought so, and I don’t think there is a way to do it, my point
>>> was really just that your swift doc comments weren’t clear on that
>>> point, then I went off at a bit of a tangent ;)
>>> 
>> No problem! What I am trying to figure out here is how we should
>> implement the lowerBound and upperBound functions. Should they
>> exactly reflect their C++ counterparts?
>> Anyway, it seems all of our implementations have the same problem,
>> that they cannot be univocally called with any predicate whatsoever,
>> (or at least it seemed to me during some tests with the
>> implementations :) ), so I don’t really know how we should act. I am
>> a little blocked.
>> Does anyone have ideas on how that could work no matter what predicate is given? Especially, an upperBound() function, which is a little trickier. 
>
> The key is to use a binary predicate (as used in sort and partition)
> instead of a unary predicate. Then you can use the predicate as is for
> lowerBound or with the arguments "reversed" for upperBound. The
> methods would have a similar signature to indexOf—one that just takes
> a value for comparable collections and one that takes a value and a
> predicate.

Having an overload that accepts a binary predicate is certainly a nice
convenience, but the most general formulation takes a unary predicate
that “partitions” the collection, i.e. returns false for the first N
elements of the collection and returns true for the rest.  

IMO it's important to expose the unary predicate version.  Lots of
times, the thing you want to compare against doesn't have the same type
as the elements of the collection.  For example, you might have a
collection of key-value pairs where you just want to compare against the
keys, and you may not even be able to create an instance of the whole
element.  For more on this, see
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2001/n1313.html

-- 
Dave