在 Rust 中推广迭代方法

Question

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

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

假设我还有一个 SuperList，它是 SubLists:

的自定义集合

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 方法来抽象 SubList 和 SuperList 的 bars 方法而不使用动态派遣？

Answer 1

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

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

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

正如您凭直觉尝试的那样，impl Trait in return 类型位置将是此处显而易见的解决方案。但正如您所注意到的，它不起作用：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 [...]

之所以设置这些初始限制，是因为实现此功能的类型级机制 was/is 尚未到位：

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 在 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 块都可以选择不同的 return 类型，只要它实现了特征。那么为什么 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 in type aliases!

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 fns 也被此阻止，因为它们基本上是 desugar 到方法 returning impl Future<Output = ...> 中。这些也是一个非常受欢迎的功能。

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

在 Rust 中推广迭代方法

Generalizing iteraton method in Rust

traits

rust