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

[Dave Abrahams]

on Fri Mar 25 2016, Jeff Hajewski <swift-evolution at swift.org> wrote:

> Dave,
>
> I've been giving this approach a lot of thought (and have read everything
> I've been able to find that you've written on the matter several times) and
> am not convinced it will work. Implementing a lowerBound function is
> trivial with a unary operator. However, implementing an upperBound or
> binarySearch function is, at least in my mind, a bit more difficult. 

upperBound is just lowerBound with an inverted predicate.  You can prove
this to yourself by looking at the implementation of any C++ standard
library.

> The reason is because with the unary predicate we only know if an
> element is strictly less than the search value or greater than or
> equal to the search value, whereas in the standard approach we can
> determine strictly greater than as well as equivalence by swapping the
> inputs to the comp function.
>
> For example, consider the set [2, 1, 5, 4]. If we want to search the set
> using a unary predicate for 3, we would pass in the closure { $0 < 3  }. I
> don't see how we can test for equivalence when all we know is "<" or ">=".
> With the standard approach using a binary predicate of `{ $0 < $1 }` we can
> use `{ $0 < 3 }` to get the lower bound and then `!{ 3 < $0 }` to get us to
> equivalence (or in this case, to return `false`).
>
> Of course, an easy solution around this is to change the definition of the
> unary predicate to return a triple of values less/equal/greater. However,
> this would either require an additional datatype to the library (which I
> don't think is appropriate) OR require the user to increase the complexity
> of their predicate function to return -1/0/1. I don't think either of these
> are ideal or necessarily better than the standard approach of a value and a
> binary predicate.
>
> I really like the idea of the unary predicate approach, I just can't seem
> to understand how it will work in practice. What am I missing here?
> (hopefully not something completely obvious!)

This works; when I get some more time I might code it up for you, if
nobody has done it by then.

> Thanks!
> Jeff
>
> On Thu, Mar 24, 2016 at 4:52 PM, Dave Abrahams via swift-evolution <
> swift-evolution at swift.org> wrote:
>
>>
>> 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
>>
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

-- 
Dave