slice::sort_by_key has more restrictions than slice::sort_by

[shepmaster]

I expected that these invocations of sort_by and sort_by_key would be equivalent:

struct Client(String);

impl Client {
    fn key(&self) -> &str {
        &self.0
    }
}

fn main() {
    let mut clients: Vec<Client> = vec![];

    // Error: cannot infer an appropriate lifetime for autoref due to conflicting requirements
    clients.sort_by_key(|c| c.key());

    // OK
    clients.sort_by(|a, b| a.key().cmp(&b.key()));
}

The implementation of sort_by_key:

pub fn sort_by_key<B, F>(&mut self, mut f: F)
    where F: FnMut(&T) -> B, B: Ord
{
    self.sort_by(|a, b| f(a).cmp(&f(b)))
}

An initial attempt at using HRTB didn't seem to pan out:

pub fn sort_by_key<B, F>(&mut self, mut f: F)
    where for <'a> F: FnMut(&'a T) -> B + 'a,
          B: Ord

[hanna-kruppe]

I think this requires HKT (specifically, type parameters of kind lifetime -> *). For the sort_by_key call to be okay, the lifetime of the input reference ('a in the HRTB example) needs to be incorporated into B to make the return type &'a str, but B is a type parameter. The usual workarounds (impl<'a> IntoIterator for &'a Collection, hard-coding the return type to be a reference as in Deref) don't seem to apply.

[shepmaster]

I think this requires HKT

I was rather afraid of that.

[oli-obk]

fn my_sort_by_key<'a, B, F>(&mut self, f: F) where
    B: 'a + Ord,
    T: 'a,
    F: FnMut(&'a T) -> B;

Works just fine. But I might've missed some fancy interaction with other code, so maybe it's a breaking change.

[shepmaster]

@oli-obk did you try implementing the body of that function?

trait MySortByKey<T> {
    fn my_sort_by_key<'a, B, F>(&mut self, f: F)
    where
        B: 'a + Ord,
        T: 'a,
        F: FnMut(&'a T) -> B;
}

impl<T> MySortByKey<T> for [T] {
    fn my_sort_by_key<'a, B, F>(&mut self, f: F)
    where
        B: 'a + Ord,
        T: 'a,
        F: FnMut(&'a T) -> B,
    {
        let a = f(&self[0]);
        let b = f(&self[1]);
        
        match a.cmp(&b) {
            _ => self.swap(0, 1),
        }
    }
}

fn main() {}

error[E0495]: cannot infer an appropriate lifetime for borrow expression due to conflicting requirements
  --> src/main.rs:16:19
   |
16 |         let a = f(&self[0]);
   |                   ^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 10:5...
  --> src/main.rs:10:5
   |
10 | /     fn my_sort_by_key<'a, B, F>(&mut self, f: F)
11 | |     where
12 | |         B: 'a + Ord,
13 | |         T: 'a,
...  |
21 | |         }
22 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:16:19
   |
16 |         let a = f(&self[0]);
   |                   ^^^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the method body at 10:5...
  --> src/main.rs:10:5
   |
10 | /     fn my_sort_by_key<'a, B, F>(&mut self, f: F)
11 | |     where
12 | |         B: 'a + Ord,
13 | |         T: 'a,
...  |
21 | |         }
22 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:16:19
   |
16 |         let a = f(&self[0]);
   |                   ^^^^^^^^

With your proposed signature, the caller of my_sort_by_key gets to specify the lifetime 'a which then must be constant during execution. However, the point of sorting is to move the items, changing their address and invalidating any lifetimes.

To do it, we need a way to say something like "there's a lifetime for each call to f and its return value which is disjoint from the passed in value and there's a generic type returned that respects that lifetime". Some made-up syntax like

F: for <'a> FnMut(&'a T) -> (B: Ord + 'a), 

[oli-obk]

Right, we can get around that with an intermediate trait:

trait MySortByKey<T> {
    fn my_sort_by_key<B, F>(&mut self, f: F)
    where
        B: Ord,
        F: for<'a> BorrowFn<'a, T, B>;
}

trait BorrowFn<'a, T: 'a, B: 'a>: FnMut(&'a T) -> B {}
impl<'a, T: 'a, B: 'a, F: FnMut(&'a T) -> B> BorrowFn<'a, T, B> for F {}

impl<T> MySortByKey<T> for [T] {
    fn my_sort_by_key<B, F>(&mut self, mut f: F)
    where
        B: Ord,
        F: for<'a> BorrowFn<'a, T, B>,
    {
        let a = f(&self[0]);
        let b = f(&self[1]);
        
        match a.cmp(&b) {
            _ => self.swap(0, 1),
        }
    }
}

fn main() {}

We can even make the intermediate trait unnameable: https://play.rust-lang.org/?gist=1039579366cc210732d3e4672b519370&version=stable

[shepmaster]

make the intermediate trait unnameable

Can you expand a bit more on what you mean by that? It would be nice if you'd also show an example usage of it. I tried with

fn main() {
    let mut a = [1,3,2];
    a.sort_by_key(|x| x);
    a.my_sort_by_key(|x| x);
}

And both failed (my_sort_by_key with one of those reallllly ugly errors).

[clarfonthey]

Perhaps a workaround is to add a sort_by_field version of sort_by_key which does exactly the same thing, only returning &K instead of K from the function.

[NovemberZulu]

I stumbled upon very similar issue while trying to sort by String field in a struct and ended up writing small wrappers like @clarcharr suggested. See https://play.rust-lang.org/?gist=906555798c392e3787a5eea151595c15&version=stable as an example. Does it make sense to develop this into a pull request?