Why can't I use a key function that returns a link when sorting a vector with sort_by_key?

Question

I am trying to sort a Vec<String> using a key function that returns links to strings in a vector. An invented example is to use the identity function as a key function (which, of course, is useless, but this is a minimal example to reproduce my problem):

 fn key(x: &String) -> &String { x } 

Now given items: Vec<String> , I would like to do

 items.sort_by_key(key); 

This gives the following error:

 error[E0271]: type mismatch resolving 'for<'r> <fn(&std::string::String) -> &std::string::String {main::key} as std::ops::FnOnce<(&'r std::string::String,)>>::Output == _' --> src/main.rs:19:11 | 19 | items.sort_by_key(key); | ^^^^^^^^^^^ expected bound lifetime parameter, found concrete lifetime | = note: concrete lifetime that was found is lifetime '_#16r 

I do not understand why I am getting this error, so I tried to track this. First I implemented my own version of sort_by_key() :

 fn sort_by_key<T, K: Ord>(a: &mut [T], key: fn(&T) -> K) { a.sort_by(|x, y| key(x).cmp(&key(y))); } 

When I try to call this function, I get what looks like the "opposite" error:

 error[E0308]: mismatched types --> src/main.rs:22:29 | 22 | sort_by_key(&mut items, key); | ^^^ expected concrete lifetime, found bound lifetime parameter | = note: expected type 'fn(&std::string::String) -> _' found type 'fn(&std::string::String) -> &std::string::String {main::key}' 

I can make this code compiled by setting the key type to &T instead of using the universal parameter K , or using &K instead of K as the return type for the key function:

 fn sort_by_key_v2<T: Ord>(a: &mut [T], key: fn(&T) -> &T) { a.sort_by(|x, y| key(x).cmp(&key(y))); } fn sort_by_key_v3<T, K: Ord>(a: &mut [T], key: fn(&T) -> &K) { a.sort_by(|x, y| key(x).cmp(&key(y))); } 

I also tried to add life time annotations, but this only shifted the error, but did not fix it.

There are three versions of the sort_by_key() function on the playground .

Why am I getting these errors? Is there a way to fix them while keeping the key type K completely universal?

Answer 1

For now, you should use the "long" form:

 v.sort_by(|x, y| key(x).cmp(&key(y))); 

Why am I getting these errors? Is there any way to fix them?

The reason and the correction is the same: Rust is currently just not expressive enough to represent what you want. The required function is called the common associated types (GAT) ; formerly known as associated type constructors (ATC) or higher genus types (HKT).

From a related problem :

For the sort_by_key call sort_by_key be in order, the lifetime of the input link [...] must be included in B to make the return type &'a str , but B is a type parameter.

I don’t know if the signature for sort_by_key smoothly move to the GAT when they are implemented.

---

In such cases, when you control the signature of all types, you may require that the link be returned:

 use std::cmp::Ordering; struct User { name: String, } fn compare_keys<T, R>(a: T, b: T, key: impl Fn(&T) -> &R) -> Ordering where for<'a> &'a R: Ord, { let ak = key(&a); let bk = key(&b); ak.cmp(&bk) } fn main() { let alice = User { name: String::from("alice"), }; let bob = User { name: String::from("bob"), }; compare_keys(alice, bob, |u| &u.name); } 

This is imperfect, because now you cannot return a non-link, but there is simply no complete solution until the GAT is implemented. You can add parallel methods such as sort_by and sort_by_key , depending on your case.

Answer 2

As @Shepmaster explained , you cannot have a sort_by_key function that handles the common associated lifetimes for the return type of the key function, but here's the option for the key function that always returns a link:

 fn sort_by_key_ref<T, F, K>(a: &mut [T], key: F) where F: Fn(&T) -> &K, K: ?Sized + Ord, { a.sort_by(|x, y| key(x).cmp(key(y))); } 

You can also write down the life requirements for a key function:

  for<'a> F: Fn(&'a T) -> &'a K, 

See an example on the playground .