How to fold vector of vector in rust?

Question

I have a vector of vector like the following.

    let m: Vec<Vec<u64>> = vec![
        vec![1, 2, 3, 4, 5],
        vec![1, 2, 3, 4, 5],
        vec![1, 2, 3, 4, 5],
        vec![1, 2, 3, 4, 5],
        vec![1, 2, 3, 4, 5]
    ];

And add function that is intended add each element of two vector.

fn add(xs: &Vec<u64>, ys: &Vec<u64>) -> Vec<u64> {
    xs.iter().zip(ys.iter()).map(|(x, y)| x + y).collect()
}

Now, I want to fold the vector of vector m.

What I tried is:

    let s: Vec<u64> = m[1..]
        .iter()
        .fold(m[0], |acc, xs| add(&acc, xs));

But this code doesn't pass the compiler.

   |
16 |         .fold(m[0], |acc, xs| add(&acc, xs));
   |               ^^^^ move occurs because value has type `Vec<u64>`, which does not implement the `Copy` trait

I tried prepend & but the compiler still rejects:

   |
16 |         .fold(&m[0], |acc, xs| add(&acc, xs));
   |               ^^^^^ expected struct `Vec`, found `&Vec<u64>`
   |
   = note: expected struct `Vec<u64>`
           found reference `&Vec<u64>`
help: consider removing the borrow
   |
16 -         .fold(&m[0], |acc, xs| add(&acc, xs));
16 +         .fold(m[0], |acc, xs| add(&acc, xs));
   |

I think the signature of add function is correct as it doesn't want to take ownership of the arguments vectors, and it returns a new vector so the ownership should be passed to the caller.

Actually, I tried every possible combinations (add/remove & from the function, etc.), but couldn't make the code pass the compiler.

Can you let me know what I missed, what is wrong with the above code? Thanks.

Answer 1

The first argument of fold must be the same type as its output. Therefore your suggestion of passing & m[0], which has type & Vec<u64>, won't work, since you want the fold to return Vec<u64> (notice value vs borrowed value). And using m[0] (without borrowing) won't work because you would be trying to move from a vector that is later used (in the iteration itself).

One option could be to start with m[0].clone() as the initial value. That does involve a cloning, obviously, but you need to allocate your output somehow anyway, so you can't do better. This works:

let s: Vec<u64> = m[1..].iter().fold(m[0].clone(), |acc, xs| add(& acc, xs));

---

Unrelatedly: I suggest you change add to have the more general signature fn add(xs: & [u64], ys: & [u64]) -> Vec<u64>. You can still use it the way you are (because & Vec<u64> coerces into & [u64]), but it's more general, because other types coerce into & [u64] too.

Answer 2

Use something like

let first = m.pop().unwrap();
let s: Vec<u64> = m
        .iter()
        .fold(first, |acc, xs| add(&acc, xs));

this avoids cloning the first argument. It assumes that the order of the operation does not matter.