<div dir="ltr">Dave,<div><br></div><div>I&#39;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 -&gt; Bool) -&gt; Index</div><div>upperBound(isOrderedBelow: Self.Collection.Element -&gt; Bool) -&gt; Index</div><div>binarySearch(isOrderedBelow: Self.Collection.Element -&gt; Bool) -&gt; Bool<br><div class="gmail_extra"><br></div><div class="gmail_extra">That&#39;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 &lt; $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&#39;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">&lt;<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>&gt;</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 &lt;<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>&gt; wrote:<br>
<br>
&gt; Dave,<br>
&gt;<br>
&gt; I&#39;ve been giving this approach a lot of thought (and have read everything<br>
&gt; I&#39;ve been able to find that you&#39;ve written on the matter several times) and<br>
&gt; am not convinced it will work. Implementing a lowerBound function is<br>
&gt; trivial with a unary operator. However, implementing an upperBound or<br>
&gt; 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&#39;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&#39;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&#39;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&#39;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>
&gt; The reason is because with the unary predicate we only know if an<br>
&gt; element is strictly less than the search value or greater than or<br>
&gt; equal to the search value, whereas in the standard approach we can<br>
&gt; determine strictly greater than as well as equivalence by swapping the<br>
&gt; inputs to the comp function.<br>
&gt;<br>
&gt; For example, consider the set [2, 1, 5, 4]. If we want to search the set<br>
&gt; using a unary predicate for 3, we would pass in the closure { $0 &lt; 3  }. I<br>
&gt; don&#39;t see how we can test for equivalence when all we know is &quot;&lt;&quot; or &quot;&gt;=&quot;.<br>
&gt; With the standard approach using a binary predicate of `{ $0 &lt; $1 }` we can<br>
&gt; use `{ $0 &lt; 3 }` to get the lower bound and then `!{ 3 &lt; $0 }` to get us to<br>
&gt; equivalence (or in this case, to return `false`).<br>
&gt;<br>
&gt; Of course, an easy solution around this is to change the definition of the<br>
&gt; unary predicate to return a triple of values less/equal/greater. However,<br>
&gt; this would either require an additional datatype to the library (which I<br>
&gt; don&#39;t think is appropriate) OR require the user to increase the complexity<br>
&gt; of their predicate function to return -1/0/1. I don&#39;t think either of these<br>
&gt; are ideal or necessarily better than the standard approach of a value and a<br>
&gt; binary predicate.<br>
&gt;<br>
&gt; I really like the idea of the unary predicate approach, I just can&#39;t seem<br>
&gt; to understand how it will work in practice. What am I missing here?<br>
&gt; (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 &quot;greater than or equal&quot;.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
&gt; Thanks!<br>
&gt; Jeff<br>
&gt;<br>
&gt; On Thu, Mar 24, 2016 at 4:52 PM, Dave Abrahams via swift-evolution &lt;<br>
&gt; <a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>&gt; wrote:<br>
&gt;<br>
&gt;&gt;<br>
&gt;&gt; on Tue Mar 15 2016, Nate Cook &lt;<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>&gt; wrote:<br>
&gt;&gt;<br>
&gt;&gt; &gt;&gt; On Mar 15, 2016, at 1:58 PM, Lorenzo Racca via swift-evolution &lt;<br>
&gt;&gt; <a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>&gt; wrote:<br>
&gt;&gt; &gt;&gt;<br>
&gt;&gt; &gt;&gt;&gt; On Mar 15, 2016, at 6:49 PM, Haravikk<br>
&gt;&gt; &gt;&gt;&gt; &lt;<a href="mailto:swift-evolution@haravikk.me" target="_blank">swift-evolution@haravikk.me</a><br>
&gt;&gt; &gt;&gt;&gt; &lt;mailto:<a href="mailto:swift-evolution@haravikk.me" target="_blank">swift-evolution@haravikk.me</a>&gt;&gt;<br>
&gt;&gt; &gt;<br>
&gt;&gt; &gt;&gt;&gt; wrote:<br>
&gt;&gt; &gt;&gt;&gt;<br>
&gt;&gt; &gt;&gt;&gt;&gt; On 15 Mar 2016, at 15:48, Lorenzo Racca &lt;<a href="mailto:lorenzo.racca@live.it" target="_blank">lorenzo.racca@live.it</a><br>
&gt;&gt; &lt;mailto:<a href="mailto:lorenzo.racca@live.it" target="_blank">lorenzo.racca@live.it</a>&gt;&gt; wrote:<br>
&gt;&gt; &gt;&gt;&gt;&gt;<br>
&gt;&gt; &gt;&gt;&gt;&gt; I already knew the impossibility of applying such a predicate as “$0<br>
&gt;&gt; == 3” and I actually couldn’t quite figure out a solution.<br>
&gt;&gt; &gt;&gt;&gt;<br>
&gt;&gt; &gt;&gt;&gt; I thought so, and I don’t think there is a way to do it, my point<br>
&gt;&gt; &gt;&gt;&gt; was really just that your swift doc comments weren’t clear on that<br>
&gt;&gt; &gt;&gt;&gt; point, then I went off at a bit of a tangent ;)<br>
&gt;&gt; &gt;&gt;&gt;<br>
&gt;&gt; &gt;&gt; No problem! What I am trying to figure out here is how we should<br>
&gt;&gt; &gt;&gt; implement the lowerBound and upperBound functions. Should they<br>
&gt;&gt; &gt;&gt; exactly reflect their C++ counterparts?<br>
&gt;&gt; &gt;&gt; Anyway, it seems all of our implementations have the same problem,<br>
&gt;&gt; &gt;&gt; that they cannot be univocally called with any predicate whatsoever,<br>
&gt;&gt; &gt;&gt; (or at least it seemed to me during some tests with the<br>
&gt;&gt; &gt;&gt; implementations :) ), so I don’t really know how we should act. I am<br>
&gt;&gt; &gt;&gt; a little blocked.<br>
&gt;&gt; &gt;&gt; Does anyone have ideas on how that could work no matter what predicate<br>
&gt;&gt; is given? Especially, an upperBound() function, which is a little trickier.<br>
&gt;&gt; &gt;<br>
&gt;&gt; &gt; The key is to use a binary predicate (as used in sort and partition)<br>
&gt;&gt; &gt; instead of a unary predicate. Then you can use the predicate as is for<br>
&gt;&gt; &gt; lowerBound or with the arguments &quot;reversed&quot; for upperBound. The<br>
&gt;&gt; &gt; methods would have a similar signature to indexOf—one that just takes<br>
&gt;&gt; &gt; a value for comparable collections and one that takes a value and a<br>
&gt;&gt; &gt; predicate.<br>
&gt;&gt;<br>
&gt;&gt; Having an overload that accepts a binary predicate is certainly a nice<br>
&gt;&gt; convenience, but the most general formulation takes a unary predicate<br>
&gt;&gt; that “partitions” the collection, i.e. returns false for the first N<br>
&gt;&gt; elements of the collection and returns true for the rest.<br>
&gt;&gt;<br>
&gt;&gt; IMO it&#39;s important to expose the unary predicate version.  Lots of<br>
&gt;&gt; times, the thing you want to compare against doesn&#39;t have the same type<br>
&gt;&gt; as the elements of the collection.  For example, you might have a<br>
&gt;&gt; collection of key-value pairs where you just want to compare against the<br>
&gt;&gt; keys, and you may not even be able to create an instance of the whole<br>
&gt;&gt; element.  For more on this, see<br>
&gt;&gt; <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">&gt;&gt;<br>
&gt;&gt; --<br>
&gt;&gt; Dave<br>
&gt;&gt;<br>
&gt;&gt; _______________________________________________<br>
&gt;&gt; swift-evolution mailing list<br>
&gt;&gt; <a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a><br>
&gt;&gt; <a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br>
&gt;&gt;<br>
&gt; _______________________________________________<br>
&gt; swift-evolution mailing list<br>
&gt; <a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a><br>
&gt; <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>