Is it possible to use a fold with a Vec?

Question

I was thinking about how to implement Fibonacci in Rust, and thought I could do it with a fold.

What I came up with is the following:

// Editor's note: this code sample predates Rust 1.0 and 
// is not valid syntax. The concepts remain valid.

range(2, generations).fold(vec![1u, 1], |data: &mut Vec<uint>, value| {
    data.push(data[-2] + data[-1]);

    data
}).last()

However, this does not compile because I can't get data into the fold in a way the borrow checker likes. Either it is immutable, or it is borrowed multiple times or then the last data is out of scope and I can't return data to fold.

Is there a way to use fold with a Vec? Or do I have to resort to to a loop?

Answer 1

Here's a working version:

fn main() {
    let z = (2..12).fold(vec![1u64, 1], |mut data, _| {
        data.push(data[data.len() - 2] + data[data.len() - 1]);
        data
    });
    println!("{:?}", z.last())
}

There are a few problems with your approach:

1. data: &mut Vec<uint> (or usize in modern Rust) — Your accumulator variable isn't a "reference to a mutable vector", it's just a "mutable vector".
2. data[-2] — Rust doesn't implicitly index from the back of the array for negative values. In fact, the index doesn't even accept negative values! It wants a usize, so your -2 and -1 would have become very large numbers!