<div dir="ltr">Dave,<div><br></div><div>I've responded below, but just for the sake of being explicit, this is roughly </div><div>the signature for lowerBound, upperBound, and binarySearch I have in </div><div>mind based on your comments of a unary predicate:</div><div><br></div><div>lowerBound(isOrderedBelow: Self.Collection.Element -> Bool) -> Index</div><div>upperBound(isOrderedBelow: Self.Collection.Element -> Bool) -> Index</div><div>binarySearch(isOrderedBelow: Self.Collection.Element -> Bool) -> Bool<br><div class="gmail_extra"><br></div><div class="gmail_extra">That's the general structure - the key is that the exact same predicate is</div><div class="gmail_extra">used in all signatures. The predicate would be defined along the lines of</div><div class="gmail_extra">a binary predicate where one of the parameters is fixed as the search value.</div><div class="gmail_extra">The unary predicate could be formed along the lines of:</div><div class="gmail_extra"><br></div><div class="gmail_extra">let binaryPred = { $0 < $1 }</div><div class="gmail_extra">let unnaryPred = binaryPred($0, value)</div><div class="gmail_extra"><br></div><div class="gmail_extra">where value is the search value. The main point of illustrating that is that</div><div class="gmail_extra">once the unary predicate is defined, we can't change the position of the</div><div class="gmail_extra">search value within the predicate like they do in the C++ implementation.</div><div class="gmail_extra"><br></div><div class="gmail_extra">Additional comments below..</div><div class="gmail_extra"><br></div><div class="gmail_extra">Thanks for your input on this! It is greatly appreciated!</div><div class="gmail_extra">Jeff</div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Mar 28, 2016 at 3:39 PM, Dave Abrahams via swift-evolution <span dir="ltr"><<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><br>
on Fri Mar 25 2016, Jeff Hajewski <<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>> wrote:<br>
<br>
> Dave,<br>
><br>
> I've been giving this approach a lot of thought (and have read everything<br>
> I've been able to find that you've written on the matter several times) and<br>
> am not convinced it will work. Implementing a lowerBound function is<br>
> trivial with a unary operator. However, implementing an upperBound or<br>
> binarySearch function is, at least in my mind, a bit more difficult.<br>
<br>
upperBound is just lowerBound with an inverted predicate. You can prove<br>
this to yourself by looking at the implementation of any C++ standard<br>
library.<br></blockquote><div><br></div><div>I've spent a decent amount of time looking at the implementation in C++, but</div><div>the caveat is that the operator is binary, and that is used in the upperBound</div><div>implementation. For upperBound we need the position of the first element</div><div>that is strictly great than the partition point, and we can't get this by simply</div><div>taking the complement of the unary predicate. In C++ they swap the order</div><div>of the parameters in the comp method to achieve this, but this isn't possible</div><div>in the unary case or, if it is, no one I have spoken with (including the four</div><div>of us discussing and working on this fix) can figure out how.</div><div><br></div><div>It occurs to me that this could be a communication issue. What I presume</div><div>you are suggesting is using a unary predicate such that the same predicate</div><div>is interchangeable amongst lowerBound, upperBound, and binarySearch.</div><div>Of course, if lowerBound and upperBound take different partition predicates</div><div>then the problem is trivial, but it also doesn't help you in implementing a </div><div>binary search.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
> The reason is because with the unary predicate we only know if an<br>
> element is strictly less than the search value or greater than or<br>
> equal to the search value, whereas in the standard approach we can<br>
> determine strictly greater than as well as equivalence by swapping the<br>
> inputs to the comp function.<br>
><br>
> For example, consider the set [2, 1, 5, 4]. If we want to search the set<br>
> using a unary predicate for 3, we would pass in the closure { $0 < 3 }. I<br>
> don't see how we can test for equivalence when all we know is "<" or ">=".<br>
> With the standard approach using a binary predicate of `{ $0 < $1 }` we can<br>
> use `{ $0 < 3 }` to get the lower bound and then `!{ 3 < $0 }` to get us to<br>
> equivalence (or in this case, to return `false`).<br>
><br>
> Of course, an easy solution around this is to change the definition of the<br>
> unary predicate to return a triple of values less/equal/greater. However,<br>
> this would either require an additional datatype to the library (which I<br>
> don't think is appropriate) OR require the user to increase the complexity<br>
> of their predicate function to return -1/0/1. I don't think either of these<br>
> are ideal or necessarily better than the standard approach of a value and a<br>
> binary predicate.<br>
><br>
> I really like the idea of the unary predicate approach, I just can't seem<br>
> to understand how it will work in practice. What am I missing here?<br>
> (hopefully not something completely obvious!)<br>
<br>
This works; when I get some more time I might code it up for you, if<br>
nobody has done it by then.<br></blockquote><div><br></div><div>Even just the logic for upperBound would be an immense help to us. As</div><div>I stated above, our issue is that the complement of the unary predicate</div><div>function gives us the equivalent of "greater than or equal".</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
> Thanks!<br>
> Jeff<br>
><br>
> On Thu, Mar 24, 2016 at 4:52 PM, Dave Abrahams via swift-evolution <<br>
> <a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>> wrote:<br>
><br>
>><br>
>> on Tue Mar 15 2016, Nate Cook <<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>> wrote:<br>
>><br>
>> >> On Mar 15, 2016, at 1:58 PM, Lorenzo Racca via swift-evolution <<br>
>> <a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>> wrote:<br>
>> >><br>
>> >>> On Mar 15, 2016, at 6:49 PM, Haravikk<br>
>> >>> <<a href="mailto:swift-evolution@haravikk.me" target="_blank">swift-evolution@haravikk.me</a><br>
>> >>> <mailto:<a href="mailto:swift-evolution@haravikk.me" target="_blank">swift-evolution@haravikk.me</a>>><br>
>> ><br>
>> >>> wrote:<br>
>> >>><br>
>> >>>> On 15 Mar 2016, at 15:48, Lorenzo Racca <<a href="mailto:lorenzo.racca@live.it" target="_blank">lorenzo.racca@live.it</a><br>
>> <mailto:<a href="mailto:lorenzo.racca@live.it" target="_blank">lorenzo.racca@live.it</a>>> wrote:<br>
>> >>>><br>
>> >>>> I already knew the impossibility of applying such a predicate as “$0<br>
>> == 3” and I actually couldn’t quite figure out a solution.<br>
>> >>><br>
>> >>> I thought so, and I don’t think there is a way to do it, my point<br>
>> >>> was really just that your swift doc comments weren’t clear on that<br>
>> >>> point, then I went off at a bit of a tangent ;)<br>
>> >>><br>
>> >> No problem! What I am trying to figure out here is how we should<br>
>> >> implement the lowerBound and upperBound functions. Should they<br>
>> >> exactly reflect their C++ counterparts?<br>
>> >> Anyway, it seems all of our implementations have the same problem,<br>
>> >> that they cannot be univocally called with any predicate whatsoever,<br>
>> >> (or at least it seemed to me during some tests with the<br>
>> >> implementations :) ), so I don’t really know how we should act. I am<br>
>> >> a little blocked.<br>
>> >> Does anyone have ideas on how that could work no matter what predicate<br>
>> is given? Especially, an upperBound() function, which is a little trickier.<br>
>> ><br>
>> > The key is to use a binary predicate (as used in sort and partition)<br>
>> > instead of a unary predicate. Then you can use the predicate as is for<br>
>> > lowerBound or with the arguments "reversed" for upperBound. The<br>
>> > methods would have a similar signature to indexOf—one that just takes<br>
>> > a value for comparable collections and one that takes a value and a<br>
>> > predicate.<br>
>><br>
>> Having an overload that accepts a binary predicate is certainly a nice<br>
>> convenience, but the most general formulation takes a unary predicate<br>
>> that “partitions” the collection, i.e. returns false for the first N<br>
>> elements of the collection and returns true for the rest.<br>
>><br>
>> IMO it's important to expose the unary predicate version. Lots of<br>
>> times, the thing you want to compare against doesn't have the same type<br>
>> as the elements of the collection. For example, you might have a<br>
>> collection of key-value pairs where you just want to compare against the<br>
>> keys, and you may not even be able to create an instance of the whole<br>
>> element. For more on this, see<br>
>> <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2001/n1313.html" rel="noreferrer" target="_blank">http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2001/n1313.html</a><br>
<span><font color="#888888">>><br>
>> --<br>
>> Dave<br>
>><br>
>> _______________________________________________<br>
>> swift-evolution mailing list<br>
>> <a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a><br>
>> <a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br>
>><br>
> _______________________________________________<br>
> swift-evolution mailing list<br>
> <a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a><br>
> <a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br>
<br>
--<br>
Dave<br>
<br>
_______________________________________________<br>
swift-evolution mailing list<br>
<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a><br>
<a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br>
</font></span></blockquote></div><br></div></div></div>