What is required for sort_by_key(|o| &o.key)?

language design
1

The closest I could come up with a header for this would be

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

or perhaps

fn sort_by_key<K<'_ = 'static>, F>(&self, mut f: F)
where
    F: for<'a> FnMut(&'a T) -> K<'a>,
    K<'_>: Ord,

Is there any way to represent the extraction function being allowed but not required to return a reference into the T? If you were adding that function today, would you do it this way or bake the idea of returning a self-reference into the conversion function (F: for<'a> FnMut(&'a T) -> &'a K) and tell computed comparisons to use sort_by?

1 Like
2

Could you just do this?

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

It's not parametrically polymorphic, but that should be fine in this case right?

3

Unfortunately not, since you'd get lease for the elements for the whole duration of the sort call that way, and since they are borrowed, they can't move (can't be sorted).

Since sort by key is just sugar for sort_by, were really not losing much because of this missing.

2 Likes
4

Doesn't lifetime subtyping already do this? If it allows you to return something with 'a lifetime, then you will implicitly be allowed to return 'static.

5

No, lets say instead of a reference, you want to return an iterator over the input. Generalizing this way is hard.

I think you can create a new trait,

trait IsValid<'a, T: ?Sized>: FnMut(&'a T) -> Self::Out {
    type Out: Ord;
}

impl<'a, T: ?Sized, K: Ord, F: FnMut(&'a T) -> K> trait IsValid<'a, T> for F {
    type Out = K;
}

type Out<'a, T, F> = <F as IsValid<'a, F>>::Out;

fn sort_by_key<F>(&self, mut f: F)
where
    F: for<'a> IsValid<'a, T>,

You can't name the output type directly, but you can use the typedef.

2 Likes
6

The reason I specifiy this is that today we can write (modulo some exact syntax this is unchecked)

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

which requires the returned value to be a reference. For lifetime subtyping to handle it and get the "proper" declaration I think the best declaration would probably be something like

fn sort_by_key<K, F>(&self, mut f: F)
where
    F: for<'a> FnMut(&'a T) -> K
       where K: 'a;
    K: Ord,
1 Like
7

Nice, it looks like we can turn that into a useful(?) implementation of sort_by_key. Though I gave up getting it to work for closures, they were not callable normally under the IsValid bound.

(playground link)

trait KeyFunc<'a, T: ?Sized> {
    type Key: Ord;
    fn key_of(&mut self, element: &'a T) -> Self::Key;
}

fn sort_by_key<T, F>(v: &mut [T], mut f: F)
where
    F: for<'a> KeyFunc<'a, T>
{
    v.sort_by(|a, b| Ord::cmp(&f.key_of(a), &f.key_of(b)))
}
8

Here's an almost solution that only works pre-NLL. Requiring K: 'a in the impl causes rustc to complain that the impl isn't wide enough.

9

Passing the closure through this function:

fn refmap<A: ?Sized, B: ?Sized, F>(f: F) -> F
where
    F: FnMut(&A) -> &B,
{
    f
}

is enough to type hint it to be a for<'a> type mapping, and then the borrow checker future warning disappears.

And doing other experiments with types on the closure argument seem to be a good way to generate compiler bugs.

10 
error: lifetime may not live long enough
  --> src/main.rs:43:13
   |
36 |         |element: &String| -> &str {
   |                   -           ---- return type of closure is &'2 str
   |                   |
   |                   let's call the lifetime of this reference `'1`
...
43 |             &element[bounds]
   |             ^^^^^^^^^^^^^^^^ returning this value requires that `'1` must outlive `'2`

It seems that the lifetime elision rules are different for closures? Or something weird is going on here. Why is '2 === '1 not implied here?

2 Likes
11

This is because rust infers the wrong lifetimes for the closure, it infers fn(&'a &str) -> &'a str instead of fn(&&'a str) -> &str. Creating a function with the correct signature removes the warning.

13

Is it worth filing a bug on this limitation? I feel like you should be able to write for <'a, K: Ord> or -> impl Ord and have the right thing happen.

14

I think we should get a for<lifetimes> syntax for specifying lifetimes on closures for exactly this reason.

15

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.