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

[Jeff Hajewski]

Dave,

I've responded below, but just for the sake of being explicit, this is
roughly
the signature for lowerBound, upperBound, and binarySearch I have in
mind based on your comments of a unary predicate:

lowerBound(isOrderedBelow: Self.Collection.Element -> Bool) -> Index
upperBound(isOrderedBelow: Self.Collection.Element -> Bool) -> Index
binarySearch(isOrderedBelow: Self.Collection.Element -> Bool) -> Bool

That's the general structure - the key is that the exact same predicate is
used in all signatures. The predicate would be defined along the lines of
a binary predicate where one of the parameters is fixed as the search value.
The unary predicate could be formed along the lines of:

let binaryPred = { $0 < $1 }
let unnaryPred = binaryPred($0, value)

where value is the search value. The main point of illustrating that is that
once the unary predicate is defined, we can't change the position of the
search value within the predicate like they do in the C++ implementation.

Additional comments below..

Thanks for your input on this! It is greatly appreciated!
Jeff

On Mon, Mar 28, 2016 at 3:39 PM, Dave Abrahams via swift-evolution <
swift-evolution at swift.org> wrote:

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

I've spent a decent amount of time looking at the implementation in C++, but
the caveat is that the operator is binary, and that is used in the
upperBound
implementation. For upperBound we need the position of the first element
that is strictly great than the partition point, and we can't get this by
simply
taking the complement of the unary predicate. In C++ they swap the order
of the parameters in the comp method to achieve this, but this isn't
possible
in the unary case or, if it is, no one I have spoken with (including the
four
of us discussing and working on this fix) can figure out how.

It occurs to me that this could be a communication issue. What I presume
you are suggesting is using a unary predicate such that the same predicate
is interchangeable amongst lowerBound, upperBound, and binarySearch.
Of course, if lowerBound and upperBound take different partition predicates
then the problem is trivial, but it also doesn't help you in implementing a
binary search.


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

Even just the logic for upperBound would be an immense help to us. As
I stated above, our issue is that the complement of the unary predicate
function gives us the equivalent of "greater than or equal".


>
> > 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
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160329/68cfdaad/attachment.html>