Issue with reduce() in Rust for summing square perimeters, fold() works

Question

I encountered an issue while trying to use the reduce() method in Rust to calculate the sum of perimeters of squares. The problem is based on a drawing where there are n + 1 squares arranged with side lengths following the Fibonacci sequence. For example, if n = 5, the side lengths of the squares are [1, 1, 2, 3, 5, 8]. The task is to find the sum of the perimeters of these squares.

Initially, I implemented the code using the fold() method, and it worked correctly. Here's the code snippet that uses fold():

fn perimeter(n: u64) -> u64 {
    let mut fib = vec![1, 1];
    for i in 2..=n as usize {
        fib.push(fib[i - 1] + fib[i - 2]);
    }

    // Calculate the sum of the perimeters using the fold method
    fib.iter().fold(0, |acc, val| acc + val * 4)
}

However, when I tried to refactor the code to use the reduce() method, it failed to compile. I modified the code as follows:

fn perimeter(n: u64) -> u64 {
    let mut fib = vec![1, 1];
    for i in 2..=n as usize {
        fib.push(fib[i - 1] + fib[i - 2]);
    }

    // Calculate the sum of the perimeters using the reduce method
    fib.iter().reduce(|acc, val| acc + val * 4).unwrap()
}

When using the reduce() method, I encountered the following error message:

error[E0308]: mismatched types
 --> src/lib.rs:8:34
  |
8 |     fib.iter().reduce(|acc, val| acc + val * 4).unwrap()
  |                                  ^^^^^^^^^^^^^
  |                                  |
  |                                  expected `&{integer}`, found integer
  |                                  help: consider borrowing here: `&(acc + val * 4)`

I have read the Rust documentation for reduce() and found an example where it works correctly. Here's the example from the documentation:

let reduced: i32 = (1..10).reduce(|acc, e| acc + e).unwrap();
assert_eq!(reduced, 45);

// Which is equivalent to doing it with `fold`:
let folded: i32 = (1..10).fold(0, |acc, e| acc + e);
assert_eq!(reduced, folded);

I expected the code to compile successfully and produce the same result as the fold() implementation. However, the error message suggests a mismatched type issue with the reduce() method.

I would appreciate any insights or suggestions on how to resolve this issue and successfully use the reduce() method to calculate the sum of perimeters of the squares. Alternatively, if there is a reason why reduce() cannot be used in this scenario, I would like to understand it.

Thank you in advance for your help!

Answer 1

The issue here is that fold is provided a by-value accumulator explicitly (that initial 0), so the input to each stage, and the output from each stage, is by value; everything agrees, so it's fine.

reduce is using the first output from the iterator as the first acc, and by using .iter(), you are passing it a reference to a value (one still owned by the original Vec). Since acc itself begins as such a reference to the first value in the Vec, you have the problem of receiving a reference on the first call, and trying to produce a value to be used for acc for the second call, so acc has an inconsistent type (reference on first invocation, value for all others).

The easiest solution here is to just consume the expiring Vec by using .into_iter() to iterate (and consume) the values directly, rather than iterating references to them:

fn perimeter(n: u64) -> u64 {
    let mut fib = vec![1, 1];
    for i in 2..=n as usize {
        fib.push(fib[i - 1] + fib[i - 2]);
    }

    // Calculate the sum of the perimeters using the reduce method
    fib.into_iter().reduce(|acc, val| acc + val * 4).unwrap()
    //  ^^^^^ Only change
}

Attempt This Online!

If the Vec cannot be consumed, other easy options for copyable/clonable types would be to make the iterator into a copying or cloning iterator, e.g.:

fib.iter().copied().reduce(|acc, val| acc + val * 4).unwrap()
// or
fib.iter().cloned().reduce(|acc, val| acc + val * 4).unwrap()

but frankly, fold is generally a better solution, unless you want to fail loudly when the underlying iterator is empty, since it guarantees a result (avoiding the need to .unwrap() or otherwise deal with the empty iterator case), doesn't require consuming, copying or cloning, and, as noted in the comments, actually does what you intended (computing the sum of all the values multiplied by four, where reduce fails to multiply the first value by four, since it's used as the original acc value, never as val).