How to perform a `flat_map` (or similar operation) on an iterator N times without runtime polymorphism?

Question

I want to be able to repeat a process where a collection that we are iterating over is altered an n number of times. n is only known at runtime, and can be specified by the user, so we cannot hard-code it into the type.

An approach that uses intermediate data structures by collect-ing between iterations is possible, like so:

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;
    }
}

However, this seems wasteful, because we are creating intermediate datastructures, so I went on looking for a solution that chains iterators directly.

At first I thought one could just do something like:

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

However, this does not work because in Rust, all functions on iterators return their own kind of 'compound iterator' struct. (In for instance Haskell, functions on iterators return the appropriate kind of result iterator, which does not become a 'bigger and bigger compound type'.) Rewriting this as a recursive function had similar problems because (a) I was returning 'some kind of Iterator' whose type was (near?)-impossible to write out by hand because of the recursion, and (b) this type was different in the base case from the recursive case.

I found this question about conditionally returning either one or the other iterator type, as well as using impl Iterator to indicate that we return some concrete type that implements the Iterator trait, but we do not care about its exact nature. A similar example to the code in the linked answer has been implemented in the code below as maybe_flatmap. This works.

However, I don't want to run flat_map zero or one time, but rather N times on the incoming iterator. Therefore, I adapted the code to call itself recursively up to a depth of N.

Attempting to do that, then makes the Rust compiler complain with an 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>`

I am stuck.

Since regardless of how often you flat_map, the final answer is going to be an (iterator over) a vector of integers, it seems like there ought to be a way of writing this function using only a single concrete return type.

Is this possible? Is there a way out of this situation without resorting to runtime polymorphism?

I believe/hope that a solution without dynamic polymorphism (trait objects or the like) is possible because regardless of how often you call flat_map the end result should have (at least morally) have the same type. I hope there is a way to shoehorn the (non-matching) nested FlatMap struct in a matching single static type somehow.

Answer 1

Is there a way to resolve this without runtime polymorphism?

No.

To solve it using a trait object:

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

I don't know which morality to apply to type systems, but the literal size in memory is (very likely to be) different for FlatMap<...> and FlatMap<FlatMap<...>>. They are different types.

See also:

• 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?