How to create a function that creates a Cartesian product Iterator from an Iterator of Iterators?

Question

If I want to create a Cartesian product of a list of lists in Haskell, I can do this:

product [] = [[]]
product (xs:xss) = concatMap (\k -> map (k:) (product1 xss)) xs

or even this:

sequence xss

I'm trying to implement an efficient iterator that would do the same in Rust, but I'm not sure what is wrong with my attempt:

use std::iter::{empty, once};

fn product<T, I, V>(xss: I) -> Box<Iterator<Item = Iterator<Item = T>>>
where
    T: Clone,
    V: IntoIterator<Item = T>,
    I: IntoIterator<Item = V>,
{
    Box::new(xss.into_iter().fold(once(empty()), |acc, xs| {
        xs.into_iter().flat_map(|x| acc.map(|ys| ys.chain(once(x))))
    }))
}

fn main() {
    let data = vec![[1, 2, 3], [10, 20, 30], [100, 200, 300]];
    let it: Vec<Vec<u32>> = product(data).collect();
    println!("{:?}", it);
}

(playground)

Produces these errors:

error[E0308]: mismatched types
  --> src/main.rs:10:9
   |
10 |         xs.into_iter().flat_map(|x| acc.map(|ys| ys.chain(once(x))))
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `std::iter::Once`, found struct `std::iter::FlatMap`
   |
   = note: expected type `std::iter::Once<std::iter::Empty<T>>`
              found type `std::iter::FlatMap<<V as std::iter::IntoIterator>::IntoIter, std::iter::Map<std::iter::Once<std::iter::Empty<T>>, [closure@src/main.rs:10:45: 10:67 x:_]>, [closure@src/main.rs:10:33: 10:68 acc:_]>`

error[E0271]: type mismatch resolving `<std::iter::Once<std::iter::Empty<T>> as std::iter::Iterator>::Item == std::iter::Iterator<Item=T>`
  --> src/main.rs:9:5
   |
9  | /     Box::new(xss.into_iter().fold(once(empty()), |acc, xs| {
10 | |         xs.into_iter().flat_map(|x| acc.map(|ys| ys.chain(once(x))))
11 | |     }))
   | |_______^ expected struct `std::iter::Empty`, found trait std::iter::Iterator
   |
   = note: expected type `std::iter::Empty<T>`
              found type `std::iter::Iterator<Item=T>`
   = note: required for the cast to the object type `std::iter::Iterator<Item=std::iter::Iterator<Item=T>>`

error[E0277]: the trait bound `[{integer}; 3]: std::iter::Iterator` is not satisfied
  --> src/main.rs:16:29
   |
16 |     let it: Vec<Vec<u32>> = product(data).collect();
   |                             ^^^^^^^ `[{integer}; 3]` is not an iterator; maybe try calling `.iter()` or a similar method
   |
   = help: the trait `std::iter::Iterator` is not implemented for `[{integer}; 3]`
   = note: required because of the requirements on the impl of `std::iter::IntoIterator` for `[{integer}; 3]`
   = note: required by `product`

error: the `collect` method cannot be invoked on a trait object
  --> src/main.rs:16:43
   |
16 |     let it: Vec<Vec<u32>> = product(data).collect();
   |                                           ^^^^^^^

The first error is giving me the feeling that Rust cannot even create a lazily consumed iterator with fold because Empty<T> is an Iterator<Item = T> (at least conceptually), but I hope I'm wrong.

Answer 1

For what its worth, the Itertools crate implements a workable cartesian product function:

use itertools::Itertools;

let it = (0..2).cartesian_product("αβ".chars());
itertools::assert_equal(it, vec![(0, 'α'), (0, 'β'), (1, 'α'), (1, 'β')]);