如何“标记”一个类似函数的特征以选择性地并行执行？

Question

背景

我有一个谓词特征。它采用某种类型

T

并为其返回一个布尔值。

trait Predicate<T> {
  fn evaluate(&self, t: &T) -> bool;
}

我还有一个评估器，可以为每个给定的

T

评估相同的谓词。

trait Evaluator<T> {
  fn evaluate(&self, is: &[T]) -> Vec<bool>;
}

Evaluator

是针对

Predicate

实现的。它评估每个

Predicate

的

T

。

impl<T, P: Predicate<T>> Evaluator<T> for P {
  fn evaluate(&self, is: &[T]) -> Vec<bool> {
    is.iter().map(|i| self.evaluate(i)).collect()
  }
}

我还为

Predicate<T>

类型的闭包实现了

Fn(&T) -> bool

，这允许我在需要

Evaluator

时提供这样的闭包，而不是每次我想应用一些结构时创建一个结构并为其实现

Evaluator

特征不同的逻辑。

现在我可以创建一个闭包并将其传递给任何需要

Evaluator

的对象。

  let p = |i: &i32| *i > 0;
  wants_evaluator(&p);

问题

到目前为止，这个 API 非常简洁，但最近我需要为每个解决方案并行评估谓词。人造丝的逻辑本身不是问题 -

par_iter()

正是我所需要的。问题是我不想失去我方便的闭包到评估器的自动转换，因为我非常依赖它。我理想中想要实现的是这样的：

  let p = |i: &i32| *i > 0;
  let p_par = p.into_par(); // will be evaluated in parallel
  wants_evaluator(&p_par);

并行计算并不经常需要，因为对于大多数简单的谓词来说，并行化只会降低性能，但是当我需要它时，我需要它。

失败的解决方案

我尝试使用包装结构

ParPredicate

struct ParPredicate<T, P: Predicate<T>>(P, PhantomData<T>);

impl<T, P> Evaluator<T> for ParPredicate<T, P>
where
  T: Sync,
  P: Predicate<T> + Sync,
{
  fn evaluate(&self, is: &[T]) -> Vec<bool> {
    is.par_iter().map(|i| self.0.evaluate(i)).collect()
  }
}

然而，Rust 抱怨这个实现与

impl<T, P: Predicate<T>> Evaluator<T> for P { ...

冲突

conflicting implementations of trait `Evaluator<_>` for type `ParPredicate<_, _>`
downstream crates may implement trait `Predicate<_>` for type `ParPredicate<_, _>`

如果我在

T

中使用某种具体类型而不是

Predicate

，则不会出现此错误。它还破坏了

Predicate

的全部意义，因为它必须是通用的。

我还尝试使用某种类型状态模式与

Predicate

:

trait ExecutionStrategy {}

enum Sequential {}
impl ExecutionStrategy for Sequential {}

enum Parallel {}
impl ExecutionStrategy for Parallel {}

trait Predicate<ExecutionStrategy, T> {
  fn evaluate(&self, i: &T) -> bool;
}

trait Evaluator<ExecutionStrategy, T> {
  fn evaluate(&self, is: &[T]) -> Vec<bool>;
}

impl<T, P> Evaluator<Sequential, T> for P
where
  P: Predicate<Sequential, T>,
{
  fn evaluate(&self, is: &[T]) -> Vec<bool> {
    is.iter().map(|i| self.evaluate(i)).collect()
  }
}

impl<T, P> Evaluator<Parallel, T> for P
where
  T: Sync,
  P: Predicate<Parallel, T> + Sync,
{
  fn evaluate(&self, is: &[T]) -> Vec<bool> {
    is.par_iter().map(|i| self.evaluate(i)).collect()
  }
}

这里的问题是我需要以某种方式将

Predicate<Sequential, T>

转换为

Predicate<Parallel, T>

，但我不知道该怎么做，即使他们基本上有相同的联系方式。

trait IntoPar<T> {
  fn into_par(self) -> impl Predicate<Parallel, T>;
}

impl<T, P: Predicate<Sequential, T>> IntoPar<T> for P {
  fn into_par(self) -> impl Predicate<Parallel, T> {
    // now what?
  }
}

我想要的只是将某种标记附加到我的

Predicate

上，这将允许

Evaluator

根据其标记为

Predicate

实现不同的逻辑。所有这些信息都是在编译过程中收集的，我不明白为什么理论上我不能实现这一点。但我该如何做到这一点，同时保持从闭包到

Evaluator

的无缝转换？

我只想探索 Rust 类型系统的局限性。该代码将仅在我的个人项目中使用，不会在生产中使用。

Answer 1

您走在正确的道路上。要解决转换为

Parallel

的问题，需要去掉

ExecutionStrategy

中的

Predicate

（但保留

Evaluator

中）：

trait Predicate<T> {
    fn evaluate(&self, i: &T) -> bool;
}

trait Evaluator<ExecutionStrategy, T> {
    fn evaluate(&self, is: &[T]) -> Vec<bool>;
}

impl<T, P> Evaluator<Sequential, T> for P
where
    P: Predicate<T>,
{
    fn evaluate(&self, is: &[T]) -> Vec<bool> {
        is.iter().map(|i| self.evaluate(i)).collect()
    }
}

impl<T, P> Evaluator<Parallel, T> for P
where
    T: Sync,
    P: Predicate<T> + Sync,
{
    fn evaluate(&self, is: &[T]) -> Vec<bool> {
        is.par_iter().map(|i| self.evaluate(i)).collect()
    }
}

fn wants_evaluator<S, E: Evaluator<S, i32>>(evaluator: E) { ... }

但是，这会产生不良后果：所有现有的

wants_evaluator()

调用都将停止使用“需要类型注释”。

这可以通过标记类型来解决：

enum Sequential {}
enum Parallel {}

trait Predicate<T> {
    fn evaluate(&self, i: &T) -> bool;
}

trait Evaluator<ExecutionStrategy, T> {
    fn evaluate(&self, is: &[T]) -> Vec<bool>;
}

pub struct ParallelPredicate<T, P>(P, PhantomData<T>);

impl<T, P> Evaluator<Parallel, T> for ParallelPredicate<T, P>
where
    T: Sync,
    P: Predicate<T> + Sync,
{
    fn evaluate(&self, is: &[T]) -> Vec<bool> {
        is.par_iter().map(|i| self.0.evaluate(i)).collect()
    }
}

fn into_par<T, P: Predicate<T>>(predicate: P) -> ParallelPredicate<T, P> {
    ParallelPredicate(predicate, PhantomData)
}

impl<T, P> Evaluator<Sequential, T> for P
where
    P: Predicate<T>,
{
    fn evaluate(&self, is: &[T]) -> Vec<bool> {
        is.iter().map(|i| self.evaluate(i)).collect()
    }
}

fn wants_evaluator<S, E: Evaluator<S, i32>>(evaluator: E) {
    evaluator.evaluate(&[1, 2, 3]);
}

fn main() {
    wants_evaluator(|v: &i32| true);
    wants_evaluator(into_par(|v: &i32| true));
}