What is the idiomatic way to make a cartesian product iterator?

[joonazan]

let vertices = [bb.start.x, bb.end.x].iter().flat_map(|&x| {
    [bb.start.y, bb.end.y].iter().flat_map(|&y| {
        [bb.start.z, bb.end.z]
            .iter()
            .map(|&z| Vec3::new(x, y, z))
    })
});

The above code complains that temporaries are getting freed too early.

Can I make an iterator that takes ownership of the array? I guess I could chain two iter::Once.

The iterator gets consumed in the same function, so I tried the following code:

let xs = [bb.start.x, bb.end.x];
let ys = [bb.start.y, bb.end.y];
let zs = [bb.start.z, bb.end.z];

let vertices = xs.iter().flat_map(|&x| {
    ys.iter()
        .flat_map(move |&y| zs.iter().map(move |&z| Vec3::new(x, y, z)))
});

But rustc can't infer a lifetime for that.

[joonazan]

Vec's into_iter fixes most of my problems. There are issues about array's into_iter. Looks like it has been weird for a long time.

[alice]

You can use the arrayvec crate which allows creation of owned iterators without heap allocations. Alternately itertools provides a cartesian_product. Basically the issue is that you want to move the integers but not the arrays, which you should also be able to do, but I wasn't able to get it to work in the short time I have before going to bed.

[joonazan]

Now it compiles but it took some really ugly convincing to make the compiler copy bb.*

let bb2 = bb.clone();
let vertices = vec![bb.start.x, bb.end.x].into_iter().flat_map(move |x| {
    let bb3 = bb2.clone();
    vec![bb2.start.y, bb2.end.y].into_iter().flat_map(move |y| {
        vec![bb3.start.z, bb3.end.z]
            .into_iter()
            .map(move |z| Vec3::new(x, y, z))
    })
});

I have also used clone like this when passing an Arc into threads. Is there any nicer pattern?

[voidshine]

Consider:

    let xs = 0..4;
    let ys = 0..2;
    let cross = ys.flat_map(|y| xs.clone().map(move |x| (x, y)));

This is nice and elegant, requiring clone of the inner iterator only because its sequence gets repeated. But integers are a copy type, and copy types are easy. Let's use shared references to a move type instead:

    // The input collections contain custom move types:
    let xs = vec![Size2(1, 1), Size2(2, 2)];
    let ys = vec![Size2(3, 3), Size2(4, 4)];

    // But let's shadow them and work with iterators only.
    let xs = xs.iter();
    let ys = ys.iter();
    let cross = ys.flat_map(|y| xs.clone().map(move |x| (x, y)));

Cool, the same expression works here too, producing pairs of references. Maybe we're done, or maybe we want values instead:

    let cross = ys.flat_map(|y| xs.clone().map(move |x| (x.clone(), y.clone())));

The key here is to work with iterators over the collections, not the collections themselves. Only when producing final outputs do we clone the elements, because naturally they get reused across the product.

[joonazan]

@voidshine That is all good, but once you nest more it breaks down.

let xends = vec![bb.start.x, bb.end.x];
let xit = xends.iter().cloned();
let yends = vec![bb.start.y, bb.end.y];
let yit = yends.iter().cloned();
let zends = vec![bb.start.z, bb.end.z];
let zit = zends.iter().cloned();

let vertices = xit.flat_map(|x| {
    let zit = zit.clone();
    yit.clone().flat_map(move |y| {
        zit.clone().map(move |z| Vec3::new(x, y, z))
    })
});

This could be written in a much cleaner way if Rust allowed specifiying captures manually like C++.

[joonazan]

It turns out you can manually specify captures. See Baby Steps

My final code:

let xends = vec![bb.start.x, bb.end.x].into_iter();
let yends = vec![bb.start.y, bb.end.y].into_iter();
let zends = vec![bb.start.z, bb.end.z].into_iter();

let vertices = xends.flat_map(|x| {
    yends.clone().flat_map({
        let zends = &zends;
        move |y| zends.clone().map(move |z| Vec3::new(x, y, z))
    })
})

[jjpe]

What is the idiomatic way to make a cartesian product iterator?

If I need anything like that, I just use itertools, which has a function that returns an Iterator over the elements of a Cartesian product.

[voidshine]

At first, I thought of X * Y * Z as (X * Y) * Z and then it's easy to work sequentially:

let xys = ys.flat_map(|y| xs.clone().map(move |x| (x, y)));
let xyzs = zs.flat_map(|z| xys.clone().map(move |(x, y)| (x, y, z)));

This is okay for light copy types. But when using move types, it's more efficient to save cloning for the very end, so setting up the borrow is worth a little more complexity.

@joonazan That's a nice find about the capturing technique. The equivalent for what I originally wrote would be:

zs.flat_map(|z| { let xs = &xs; ys.clone().flat_map(move |y| xs.clone().map(move |x| (x, y, z))) } );

And for move types just replace the final value (x, y, z) with (x.clone(), y.clone(), z.clone()).

But it's even easier if you set up borrows to the iterators and use only move closures, because shared refs are copy types:

let xs = &xs;
let ys = &ys;
let xyzs = zs.flat_map(move |z| ys.clone().flat_map(move |y| xs.clone().map(move |x| (x, y, z))));

C++ captures are concise and powerful but a little dangerous and tricky for newcomers. In Rust I might actually prefer it if all closures were implicitly move, and borrows had to be set up by creating reference values. This would be consistent with normal function calls where parameter values (including references) always move into the function.

[joonazan]

I would also prefer move by default. It was hard to grasp when I first learned Rust closures. I think I write more move closures than ones without it.

It probably isn't going to change, though. But if someone makes a Haskell-style syntax for Rust or something like that, they could incorporate this.