generics - 为什么在使用 sort_by_key 对向量进行排序时不能使用返回引用的键函数？

Question

我正在尝试对 Vec<String> 进行排序使用返回对向量中字符串的引用的键函数。一个人为的例子是使用身份函数作为关键函数(这当然是无用的，但它是重现我的问题的最小例子):

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

fn example(items: Vec<String>) {
    items.sort_by_key(key);
}

这会产生以下错误:

error[E0308]: mismatched types
   --> src/lib.rs:6:11
    |
6   |     items.sort_by_key(key);
    |           ^^^^^^^^^^^ lifetime mismatch
    |
    = note: expected associated type `<for<'r> fn(&'r String) -> &'r String {key} as FnOnce<(&String,)>>::Output`
               found associated type `<for<'r> fn(&'r String) -> &'r String {key} as FnOnce<(&String,)>>::Output`
    = note: the required lifetime does not necessarily outlive the empty lifetime
note: the lifetime requirement is introduced here

我不明白为什么我会收到这个错误，所以我试图追踪这个问题。我首先实现了自己的 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)));
}

当尝试调用这个函数时，我得到了看起来像“相反”的错误:

error[E0308]: mismatched types
 --> src/lib.rs:6:29
  |
6 |     sort_by_key(&mut items, key);
  |                             ^^^ one type is more general than the other
  |
  = note: expected fn pointer `for<'r> fn(&'r String) -> &String`
             found fn pointer `for<'r> fn(&'r String) -> &'r String`

我可以通过将 key 类型固定为 &T 来编译此代码而不是使用通用参数 K ，或使用 &K而不是 K作为键函数的返回类型:

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)));
}

我还尝试添加生命周期注释，但这只是转移了错误而没有解决它。

Here's the three versions of the sort_by_key() function on the Playground .

为什么会出现这些错误？有没有办法在保持 key 类型 K 的同时修复它们完全通用？

Answer 1

现在，您必须使用“长”形式:

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

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

原因和修复是一样的:Rust 目前的表现力不足以表达您想要的东西。所需的功能称为 generic associated types (GATs) ;以前称为关联类型构造函数 (ATC) 或更高类型 (HKT)。

来自associated issue :

For the sort_by_key call to be okay, the lifetime of the input reference [...] needs to be incorporated into B to make the return type &'a str, but B is a type parameter.

我不知道 sort_by_key 的签名在实现时是否能够无缝移动到 GAT。在这一点上似乎值得怀疑，因为 Fn* 特性本身可能需要更改。

---

在您控制所有类型签名的类似情况下，您可以要求返回一个引用:

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);
}

这是不理想的，因为现在您不能返回非引用，但在实现 GAT 之前根本没有完整的解决方案。您可以添加并行方法，如 sort_by 和 sort_by_key，具体取决于您的情况。