recursion - 如何在没有运行时多态性的情况下对迭代器执行 N 次 `flat_map`(或类似操作)？

Question

我希望能够重复一个过程，在该过程中，我们正在迭代的集合被更改 n 次。 n 仅在运行时已知，可以由用户指定，因此我们不能将其硬编码到类型中。

通过 collect 在迭代之间使用中间数据结构的方法是可能的，如下所示:

let n = 10;

let mut vec1 = vec![1, 2, 3];
{
    for _index in 0..n {
        let temp_vec = vec1.into_iter().flat_map(|x| vec![x, x * 2]).collect();
        vec1 = temp_vec;
    }
}

但是，这似乎很浪费，因为我们正在创建中间数据结构，所以我继续寻找一种直接链接迭代器的解决方案。

一开始我以为可以这样做:

let mut iter = vec![1, 2, 3].into_iter();
for index in 0..n {
    iter = iter.flat_map(|x| vec![x, x * 2].into_iter());
}

但是，这不起作用，因为在 Rust 中，迭代器上的所有函数都返回它们自己的“复合迭代器”结构。 (例如在 Haskell 中，迭代器上的函数返回适当类型的结果迭代器，它不会变成“越来越大的复合类型”。) 将其重写为递归函数也有类似的问题，因为(a)我返回的“某种迭代器”的类型(接近？) - 由于递归而无法手动写出，并且(b)这种类型在来自递归案例的基本案例。

我找到了 this question关于有条件地返回一种或另一种迭代器类型，以及使用 impl Iterator 来指示我们返回一些实现 Iterator 特性的具体类型，但我们不关心它的确切性质。 与链接答案中的代码类似的示例已在下面的代码中实现为 maybe_flatmap。这行得通。

但是，我不想运行 flat_map 零次或一次，而是希望在传入的迭代器上运行 N 次。因此，我修改了代码以递归调用自身，直到深度为 N。

尝试这样做，然后让 Rust 编译器提示 error[E0720]: opaque type expands to a recursive type:

use either::Either; // 1.5.3

/// Later we want to work with any appropriate items,
/// but for simplicity's sake, just use plain integers for now.
type I = u64;

/// Works, but limited to single level.
fn maybe_flatmap<T: Iterator<Item = I>>(iter: T, flag: bool) -> impl Iterator<Item = I> {
    match flag {
        false => Either::Left(iter),
        true => Either::Right(iter.flat_map(move |x| vec![x, x * 2].into_iter())),
    }
}

/// Does not work: opaque type expands to a recursive type!
fn rec_flatmap<T: Iterator<Item = I>>(iter: T, depth: usize) -> impl Iterator<Item = I> {
    match depth {
        0 => Either::Left(iter),
        _ => {
            let iter2 = iter.flat_map(move |x| vec![x, x * 2]).into_iter();
            Either::Right(rec_flatmap(iter2, depth - 1))
        }
    }
}

fn main() {
    let xs = vec![1, 2, 3, 4];
    let xs2 = xs.into_iter();
    let xs3 = maybe_flatmap(xs2, true);
    let xs4: Vec<_> = xs3.collect();
    println!("{:?}", xs4);

    let ys = vec![1, 2, 3, 4];
    let ys2 = ys.into_iter();
    let ys3 = rec_flatmap(ys2, 5);
    let ys4: Vec<_> = ys3.collect();
    println!("{:?}", ys4);
}

Rust playground

error[E0720]: opaque type expands to a recursive type
  --> src/main.rs:16:65
   |
16 | fn rec_flatmap<T: Iterator<Item = I>>(iter: T, depth: usize) -> impl Iterator<Item = I> {
   |                                                                 ^^^^^^^^^^^^^^^^^^^^^^^ expands to a recursive type
   |
   = note: expanded type is `either::Either<T, impl std::iter::Iterator>`

我卡住了。

因为无论您flat_map 的频率如何，最终的答案都将是一个(迭代器)一个整数向量，似乎应该有一种方法可以只使用一个具体的返回类型。

这可能吗？有没有解决这种情况的办法不求助于运行时多态性？

我相信/希望没有动态多态性(特征对象等)的解决方案是可能的，因为无论您多久调用一次 flat_map，最终结果都应该(至少在道德上)具有相同的结果类型。我希望有一种方法可以将(不匹配的)嵌套 FlatMap 结构硬塞进匹配的单个静态类型中。

Answer 1

Is there a way to resolve this without runtime polymorphism?

没有。

使用特征对象解决它:

let mut iter: Box<dyn Iterator<Item = i32>> = Box::new(vec![1, 2, 3].into_iter());
for _ in 0..n {
    iter = Box::new(iter.flat_map(|x| vec![x, x * 2].into_iter()));
}

regardless of how often you call flat_map the end result should have (at least morally) have the same type

我不知道哪种道德适用于类型系统，但是对于 FlatMap<...>，内存中的文字大小(很可能)不同。和 FlatMap<FlatMap<...>> .它们是不同的类型。

另见:

• Conditionally iterate over one of several possible iterators
• Creating Diesel.rs queries with a dynamic number of .and()'s
• How do I iterate over a Vec of functions returning Futures in Rust?
• How can I extend the lifetime of a temporary variable inside of an iterator adaptor in Rust?
• Why does Iterator::take_while take ownership of the iterator?