Update sorting infrastructure for jb/functions

[timholy]

@StefanKarpinski, while you're on "progress for 0.6" duty, I had the impression you were going to tackle this?

[Keno]

This seems like the issue to write down an issue which I've voice in person, but don't think I've written down. When using searchsortedfirst and the like, one can pass a by function, which is very convenient for searching. However, the thing one searches for in the input not the output of the by function, making usage a little awkward, since one may have to construct a dummy object. E.g. consider:

searchsortedfirst(records, SomePotentiallyHardToConstructRecord(thetimestampimlookingfor, ...), by = record->record.timestamp)

[StefanKarpinski]

Yes, this needs to be done. I've been a bit busy with Pkg3 design, so if someone else wants to have at it, they can. If that doesn't happen in the next few weeks, I'll do it.

[ViralBShah]

We may be having a couple of interns at Julia Computing perhaps in December - is this something to have them work on?

[Sacha0]

Unlikely to receive attention prior to 0.6. Best!

[ViralBShah]

Pinging @shashi here in case he can get to it.

[tkelman]

This needs to go through a Julep and major redesign.

[JeffBezanson]

Also rev::Bool = true leads to a type-instability (which in the case of the searchsorted* functions is very expensive, leading to the need for the horrible method-overwrite warnings during bootstrap). We could potentially replace this keyword argument with just order = Reverse.

[JeffBezanson]

Current situation doesn't seem so bad, and this is a bit of a project. I suggest removing from the milestone.

[timholy]

Since no one has gotten to this, I can't disagree.

[RauliRuohonen]

@StefanKarpinski said in #10593 (comment) (similarly big revamp of search/find functions):

Temporary fix if we don't get to this in time for feature freeze: move all these functions into a Search stdlib package and then fix it with a major version bump of that package in the future.

Would it be possible to do this with sort functions, so this issue could be moved to 1.x milestone instead of 2.0?

[StefanKarpinski]

We've largely decided against this because it seems like the additional structure provided by the Ordering objects is actually useful fairly often. You can't, for example, dispatch on the structure of a function object the way you can on specific kinds of Ordering objects. The main outstanding issue was type instability of the rev keyword, but that's a separate issue.