rust - Rust 中的泛化迭代方法

Question

假设我有一些 Foo 的自定义集合s:

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

假设我也有一个 SuperList这是 SubList 的自定义集合s:

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

我想定义一个提供方法的特征 items ，并在 SubList 上实现该特征和 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)

Here's a playground link to what I've tried so far
如何定义特征 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说:

Initial limitations:

impl Trait may only be written within the return type of a freestanding or inherent-impl function, not in trait definitions [...] Eventually, we will want to allow the feature to be used within traits [...]

这些最初的限制已经到位，因为完成这项工作的类型级机制还没有到位:

One important usecase of abstract return types is to use them in trait methods.

However, there is an issue with this, namely that in combinations with generic trait methods, they are effectively equivalent to higher kinded types. Which is an issue because Rust's HKT story is not yet figured out, so any "accidental implementation" might cause unintended fallout.

The following explanation in the RFC也值得一读。
也就是说， impl Trait 的一些用途今天已经可以实现 in traits:使用关联类型!考虑一下:

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 block 可以选择不同的返回类型，只要它实现了一个 trait。那么为什么 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 尚未完全实现，当然还不稳定。见 the tracking issue .
但即使使用 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)
    }
}

这确实有效! (再次，在夜间，具有这些不稳定的功能。)您可以看到完整的工作示例 in this playground .
这种类型系统的工作已经进行了很长时间，似乎正在慢慢达到可以使用的状态。 (我很高兴^_^)。我希望在不久的将来，一些基本功能，或者至少是其中的子集，会稳定下来。一旦这些在实践中被使用并且我们看到它们是如何工作的，更多的便利特性(如特性中的 impl Trait)将被重新考虑和稳定。或者我认为是这样。
另外值得注意的是 async fn s 中的 s 也被这个阻止了，因为它们基本上是一个返回 impl Future<Output = ...> 的方法。 .这些也是一个非常需要的功能。

总结 :这些限制一直是一个痛点，并且它们在不同的实际情况(异步、流迭代器、您的示例……)中重新出现。我没有参与编译器开发或语言团队的讨论，但我已经关注这个话题很长时间了，我认为我们已经接近最终解决很多这些问题了。当然不会出现在下一个版本中，但我认为我们在 future 一两年内获得其中一些的机会很大。