Как выполнить `flat_map` (или аналогичную операцию) на итераторе N раз без полиморфизма времени выполнения?

Я хочу иметь возможность повторить процесс, в котором коллекция, которую мы повторяем, изменяется n количество раз. n известен только во время выполнения и может быть указан пользователем, поэтому мы не можем жестко запрограммировать его в тип.

Возможен подход, который использует промежуточные структуры данных путем collect-ing между итерациями, например:

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 функции на итераторах возвращают соответствующий тип итератора результата, который не становится «все большим и большим составным типом».) Переписывание этого как рекурсивной функции имело аналогичные проблемы, потому что (а) я возвращал «какой-то вид of Iterator ', тип которого был (рядом?) - невозможно было записать вручную из-за рекурсии, и (б) этот тип отличался в базовом случае от рекурсивного случая.

Я нашел этот вопрос об условном возврате одного или другого типа итератора, а также об использовании 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);
}

площадка для ржавчины

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 в соответствующий единственный статический тип.