在对一组具有高阶函数的项目进行过滤时，如何避免分配？

Question

尝试基于通用谓词过滤一组项目，因为在运行时计算：

fn main () {
    let el = vec![
        vec![10, 20, 30], 
        vec![40, 50, 60]
    ];
    
    println!("{:?}", use_predicate(el, a_predicate)); // [[40, 50, 60]]
}

fn a_predicate(it: &mut impl Iterator<Item = u64>) -> bool {
    it.any(|n| n > 50)
}

pub fn use_predicate<I: Iterator<Item = u64>>(
    items: Vec<Vec<u32>>, 
    predicate: impl FnMut(&mut I) -> bool
) -> Vec<Vec<u32>> {
    items
        .into_iter()
        // ISSUE HERE
        //
        // If I collect and rewrite predicate as predicat(Vec<u64>), it works,
        // however I want to avoid allocation just to iterate over the elements.
        //
        // It also works if I just call `a_predicate` directly, but I need to 
        // pass the predicate as a parameter...
        //
        // In other words, the error doesn't happen unless I have nested generics.
        .filter(|it| predicate(&mut it.iter().map(|it| *it as u64)))
        .collect::<Vec<_>>()
}

编译错误表明 rustc 无法将

u64

迭代器视为

impl Iterator<Item = u64>

.

error[E0308]: mismatched types
  --> src/main.rs:25:32
   |
10 | pub fn use_predicate<I: Iterator<Item = u64>>(
   |                      - this type parameter
...
25 |         .filter(|it| predicate(&mut it.iter().map(|it| *it as u64)))
   |                      --------- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected type parameter `I`, found struct `Map`
   |                      |
   |                      arguments to this function are incorrect
   |
   = note: expected mutable reference `&mut I`
              found mutable reference `&mut Map<std::slice::Iter<'_, u32>, [closure@src/main.rs:25:51: 25:55]>`

我不确定如何在避免收集到

Vec<_>

的同时限制类型，这是无用的成本，因为我们只需要迭代项目以进行过滤。

操场链接

---

编辑：按照下面的建议使用

dyn

并不是一个不受欢迎的解决方案，因为我确信仍然比收集到分配的堆中快得多

Vec<_>

。但是，在生产中，如果不将

predicate: FnMut

包装在

Mutex

中，并且每次必须评估谓词时解锁，我将面临一个难以解决的生命周期问题。而在这一点上，我对业绩前景并不那么乐观。

我做了另一个 playground 来更好地代表这个问题。这是通过包装在 Arc<Mutex<_>> 中

solved

的问题。 你能想出一种不使用

Mutex

的方法来解决这个问题吗？

Answer 1

不幸的是，你不能在 Rust 中表达这种类型。

首先要了解的是泛型是类型arguments。也就是说，如果函数使用泛型，则泛型的类型是函数的另一个input，但在编译时。这就是为什么我更喜欢术语“类型参数”而不是泛型，但不知何故它在函数式编程语言之外并没有流行起来。

因此，类型参数

I

是

use_predicate

的输入，并在调用站点确定。但是在函数内部，您将一种非常特定类型的迭代器传递给谓词——调用者肯定没有提供的迭代器。这就是

expected type parameter 'I', found struct 'Map'

所说的。

也许你也尝试过：

pub fn use_predicate<P>(
    items: Vec<Vec<u32>>, 
    predicate: impl FnMut(&mut impl Iterator<Item = u64>) -> bool
) -> Vec<Vec<u32>> { ... }

这是不允许的。目前可以在 Rust 中去除这种糖分的唯一方法是基本上与您在问题中给出的相同。它会有同样的问题，但也可能不是 Rust 开发人员 want 脱糖的方式。更有可能的是，他们想使用更高级别的边界对其进行脱糖：

pub fn use_predicate<P>(items: Vec<Vec<u32>>, predicate: P) -> Vec<Vec<u32>>
where
    P: for<I: Iterator<Item = u64>> FnMut(&mut I) -> bool { ... }

现在这正是您想要的！可悲的是，目前不支持此功能，而且我还没有看到对此类功能或任何实施它的热情。

---

那你能做什么？

您可以简化您的要求。但是，假设你不能，你可以使用动态调度：

fn a_predicate(mut items: &mut dyn Iterator<Item = u64>) -> bool {
    // Clunky workaround because Iterator::any isn't object-safe
    (&mut items).any(|n| n > 50)
}

pub fn use_predicate(
    items: Vec<Vec<u32>>,
    mut predicate: impl FnMut(&mut dyn Iterator<Item = u64>) -> bool,
) -> Vec<Vec<u32>> {
    items
        .into_iter()
        .filter(|items| predicate(&mut items.iter().map(|&n| n as u64)))
        .collect::<Vec<_>>()
}