Expected bound lifetime parameter, found concrete lifetime when trying to pass function that returns reference

I am trying to sort according to a function that returns a reference, but I am getting a very weird error:


error[E0271]: type mismatch resolving `for<'r> <F as std::ops::FnOnce<(&'r T,)>>::Output == _`
  --> src/../...rs:89:19
   |
89 |         self.data.sort_unstable_by_key(f);
   |                   ^^^^^^^^^^^^^^^^^^^^ expected bound lifetime parameter, found concrete lifetime

error: aborting due to previous error
impl<T: Send> Partition<T> {
    pub fn sort_by_light_key<F, K>(&mut self, f: F)
        where F: Copy + Sync + FnMut(&T) -> &K,
              K: Ord
    {
        self.data.sort_unstable_by_key(f);
    }
}

I really don't understand what the problem is here so any help would be great...

1 Like

The signature of sort_unstable_by_key() says F: FnMut(&T) -> K, whereas you have ... -> &K. If you remove the & the minimal version of the code will compile. With that out of the way, how is Copy + FnMut supposed to work?

1 Like

Well isn't the &K a restriction to a type K. It means it requires a reference of a type which is a type, so it should fit.

The reason why I want &K is because somewhere else it the code partitioning is done on the lambda function and I don't want to copy the data, rather just use a reference for performance reasons.

The type system doesn't have the subtyping flexibility you expect from it. The sort function wants F: FnMut(&T) -> K, K: Ord, and only exactly this is allowed.

In your case it's (pseudo-syntax):

F: FnMut(&T) -> Z, Z: &K, K: Ord

which means value returned from the function (Z) is not comparable any more (no Ord for Z). Dereference of that value is comparable, but the code which uses this callback won't dereference it, and therefore has no way of comparing &K.

2 Likes

Thank you for your explanation.

So the reason why this is not working is:

However I found an alternative. You can use the sort_unstable_by function. This idea came after reading this stack overflow post:

self.data.sort_unstable_by(|a, b|  f(a).cmp(f(b))  );