[swift-evolution] [Draft][Proposal] Formalized Ordering

[Dave Abrahams]

on Fri Jul 22 2016, Haravikk <swift-evolution at swift.org> wrote:

> Definitely a +1 from me, in fact I've implemented essentially this as
> an extension for my own convenience, but would definitely prefer it to
> be a proper component of the stdlib.
>
> I have some queries to raise:
>
> First is the naming, to me Ordering implies the enum itself is used
> for ordering collections but that's not really the case. 

I don't understand why you think that's implied

> In my own hacked implementation I'm using Order.before, Order.same,
> and Order.after. It's not much of a change, but it seems to clarify
> what the enum is, at least in my opinion.

I always thought the name “Order” would be perfect if it weren't so
short and likely to conflict with type names that user code will want.
We do have qualification to fall back on, so this is a judgement call.

I pretty strongly believe in the words “ascending” and “descending” for
the cases.  The result reflects the order in which the arguments to the
function appear in a call.  So if f reflects standard dictionary order, 

    f("a", "b") => ascending
    f("b", "a") => descending

> One thing I was considering, but didn't do since my extension is just
> a bolt-on for convenience, is whether the before/ascending and
> after/descending cases should contain a value, allowing
> implementations to provide a hint of how far back/forward an element
> should be. This is a hint only of course, but could be useful; for
> example, when implementing a binary search you could instead use the
> hint value to provide a (hopefully) better guess at where to jump to
> next, for example if the value is very high you might jump to a
> position forward backward/forward rather than always selecting the
> middle every time. This is what Java's Comparable type does, since it
> uses a number where negative is before, 0 is same and positive is
> after.  

I'm deeply skeptical.  I don't believe you can use this hint to do
binary search without destroying its complexity guarantee.  If you can
show me algorithms that take advantage of this hint, with demonstrations
of their correctness, I'd consider it.

> Why is Equatable in this case implemented with a static .areSame()
> method, but Comparable isn't implemented by a static .compare()
> method? Seems like they should both be the same personally.  

Because we wouldn't be able to .compare() tuples, which are not nominal
types that can be extended.  That's almost the only reason, IIRC.

> There should be a way to "flip" the operator. One thing that's great
> about the current sorting method is the ability to pass the < or >
> operators for ascending/descending respectively, we can do the first
> one by passing the <=> operator, but a flip function or something
> would be nice to, well, flip it (swap the ascending and descending
> cases before returning).
>
> Just some thoughts, but I definitely want this.
>
>> On 22 Jul 2016, at 02:11, Robert Widmann via swift-evolution
>> <swift-evolution at swift.org> wrote:
>> 
>> Hello Swift Community,
>> 
>> Harlan Haskins, Jaden Geller, and I have been working on a proposal
>> to clean up the semantics of ordering relations in the standard
>> library.  We have a draft that you can get as a
>> gist. <https://gist.github.com/CodaFi/f0347bd37f1c407bf7ea0c429ead380e>
>> Any feedback you might have about this proposal helps - though
>> please keeps your comments on Swift-Evolution and not on the gist.
>> 
>> Cheers,
>> 
>> ~Robert Widmann
>> 
>> 
>> 
>> 
>> _______________________________________________
>> 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