在 Rust 中推广迭代方法

Question

假设我有一些自定义的Foos集合：

struct Bar {}
struct Foo {
    bar: Bar
}
struct SubList {
    contents: Vec<Foo>,
}

并假设我也有一个sSuperList的自定义集合SubList：

struct SuperList {
    contents: Vec<SubList>,
}

SubList并且SuperList每个都提供一个方法bars：

impl SubList {
    fn bars(&self) -> impl Iterator<Item = &Bar> + '_ {
        self.contents.iter().map(|x| &x.bar)
    }
}
impl SuperList {
    fn bars(&self) ->  impl Iterator<Item = &Bar> + '_ {
        self.contents.iter().flat_map(|x| x.items())
    }
}

我想定义一个提供 method 的特征items，并在SubListand上实现该特征，SuperList这样SubList::items就等价于SubList::bars并且SuperList::items等价于SuperList::bars，这样我就可以做到这一点：

fn do_it<T: Buz<Bar>>(buz: &T) {
    for item in buz.items() {
        println!("yay!")
    }
}

fn main() {
    let foos = vec![Foo{ bar: Bar{} }];
    let sublist = SubList{ contents: foos };
    do_it(&sublist);
    let superlist = SuperList{ contents: vec![sublist] };
    do_it(&superlist);
}

我可以用动态调度做我想做的事：

trait Buz<T> {
    fn items(&self) -> Box<dyn Iterator<Item = &T> + '_>;
}
impl Buz<Bar> for SubList {
    fn items(&self) -> Box<dyn Iterator<Item = &Bar> + '_> {
        SubList::bars(self)
    }
}
impl Buz<Bar> for SuperList {
    fn items(&self) -> Box<dyn Iterator<Item = &Bar> + '_> {
        SuperList::bars(self)
    }
}

但是，以下方法不起作用：

trait Baz<T> {
    fn items(&self) -> impl Iterator<Item = &T> + '_;
}
impl Baz<Bar> for SubList {
    fn items(&self) -> impl Iterator<Item = &Bar> + '_ {
        SubList::bars(self)
    }
}
impl Baz<Bar> for SuperList {
    fn items(&self) -> impl Iterator<Item = &Bar> + '_ {
        SuperList::bars(self)
    }
}

(error[E0562]: `impl Trait` not allowed outside of function and inherent method return types)

这是我迄今为止尝试过的内容的游乐场链接

我如何定义一个特点Baz它提供了一个items在方法抽象bars的方法SubList和SuperList不使用动态分配？

Answer 1

不幸的是，你想要做的事情现在在 Rust 中实际上是不可能的。不是设计使然，而仅仅是因为一些相关的类型级别功能尚未实现或稳定。

除非您有空闲时间，对类型级别的东西感兴趣并且愿意每晚使用：只需使用盒装迭代器。它们很简单，只是工作，在大多数情况下，它甚至可能不会以有意义的方式损害性能。

你还在读书吗？好吧，我们来谈谈吧。

正如您直观地尝试的那样，impl Trait返回类型位置将是这里明显的解决方案。但正如您所注意到的，它不起作用：error[E0562]: `impl Trait` not allowed outside of function and inherent method return types. 这是为什么？RFC 1522说：

初始限制：

impl Trait只能在独立或固有实现函数的返回类型中编写，而不是在特征定义中编写[...]最终，我们将希望允许在特征中使用该功能[...]

这些最初的限制已经到位，因为完成这项工作的类型级别机制尚未到位：

抽象返回类型的一个重要用例是在特征方法中使用它们。

然而，这有一个问题，即与通用特征方法结合时，它们实际上等同于更高种类的类型。这是一个问题，因为 Rust 的 HKT 故事尚未弄清楚，因此任何“意外实现”都可能会导致意想不到的后果。

RFC 中的以下解释也值得一读。

也就是说，impl Traitin 特征的一些用途现在已经可以实现：使用关联类型！考虑一下：

trait Foo {
    type Bar: Clone;
    fn bar() -> Self::Bar;
}

struct A;
struct B;

impl Foo for A {
    type Bar = u32;
    fn bar() -> Self::Bar { 0 }
}

impl Foo for B {
    type Bar = String;
    fn bar() -> Self::Bar { "hello".into() }
}

这有效并且“基本上等同于”：

trait Foo {
    fn bar() -> impl Clone;
}

每个impl块都可以选择不同的返回类型，只要它实现了一个特征。那么为什么不简单impl Trait地将糖化为关联类型呢？好吧，让我们尝试一下你的例子：

trait Baz<T> {
    type Iter: Iterator<Item = &Bar>;
    fn items(&self) -> Self::Iter;
}

我们得到一个missing lifetime specifier错误：

4 |     type Iter: Iterator<Item = &Bar>;
  |                                ^ expected named lifetime parameter

尝试添加生命周期参数...我们注意到我们不能这样做。我们需要的是利用&self这里的生命周期。但此时我们无法获取它（在关联的类型定义中）。这种限制非常不幸，并且在很多情况下都会遇到（搜索术语“流迭代器”）。这里的解决方案是 GAT：通用关联类型。它们允许我们这样写：

trait Baz<T> {
    //       vvvv  That's what GATs allow
    type Iter<'s>: Iterator<Item = &'s Bar>;
    fn items(&self) -> Self::Iter<'_>;
}

GAT 尚未完全实施，而且肯定还不稳定。请参阅跟踪问题。

但即使有了 GAT，我们也无法完全让您的示例发挥作用。这是因为由于使用了闭包，您使用了不可命名的迭代器类型。因此impl Baz for ...块将无法提供type Iter<'s>定义。在这里我们可以使用另一个还不稳定的功能：impl Trait类型别名！

impl Baz<Bar> for SubList {
    type Iter<'s> = impl Iterator<Item = &'s Bar>;
    fn items(&self) -> Self::Iter<'_> {
        SubList::bars(self)
    }
}

这确实有效！（同样，每晚，具有这些不稳定的功能。）您可以在这个游乐场中看到完整的工作示例。

这个类型系统工作已经持续了很长时间，看起来正在慢慢达到可用的状态。（对此我感到非常高兴^_^）。我预计一些基本功能，或者至少是其中的子集，将在不久的将来变得稳定。一旦这些在实践中使用并且我们看到它们是如何工作的，更多便利功能（如impl Trait特征）将被重新考虑和稳定。或者说我是这么认为的。

另外值得注意的是，async fntraits 中的 s 也被此阻止，因为它们基本上脱糖为返回 的方法impl Future<Output = ...>。这些也是人们强烈要求的功能。

总之：这些限制在相当长一段时间内一直是一个痛点，并且它们在不同的实际情况中重新出现（异步、流式迭代器、您的示例……）。我没有参与编译器开发或语言团队讨论，但我长期以来一直关注这个主题，我认为我们即将最终解决许多此类问题。当然不会在下一个版本中出现，但我认为我们很有可能在未来一两年内实现这一点。