CODEWITHSUNDEEP
rustmutableborrow-checker
Gevious
Gevious

Reputation: 3252

Cannot borrow immutable borrowed HashMap cache as mutable in a recursive Fibonacci implementation

I want to implement a Fibonacci series along with caching the already calculated results. I'm not sure this approach is even possible in Rust, but its the best I've come up with. Here's the code:

use std::collections::HashMap;

pub fn fib_hash(n: u32) -> u64 {
    let mut map: HashMap<u32, u64> = HashMap::new();

    // This is the engine which recurses saving each value in the map
    fn f(map: &HashMap<u32, u64>, n: u32) -> u64 {
        let c = match map.get(&n) {
            Some(&number) => number,
            _ => 0,
        };
        if c != 0 {
            return c;
        }
        let m = match n {
            1 if n < 1 => 0,
            1...2 => 1,
            _ => f(&map, n - 1) + f(&map, n - 2),
        };
        map.insert(n, m);
        m
    }
    f(&map, n)
}

The idea is to have a "global" HashMap which can be reused. However, I'm guessing this is not really possible since we'll end up having multiple mutable borrowers for the map. This is the error I get

Rust 2015

error[E0596]: cannot borrow immutable borrowed content `*map` as mutable
  --> src/lib.rs:20:9
   |
7  |     fn f(map: &HashMap<u32, u64>, n: u32) -> u64 {
   |               ------------------ use `&mut HashMap<u32, u64>` here to make mutable
...
20 |         map.insert(n, m);
   |         ^^^ cannot borrow as mutable

Rust 2018

error[E0596]: cannot borrow `*map` as mutable, as it is behind a `&` reference
  --> src/lib.rs:20:9
   |
7  |     fn f(map: &HashMap<u32, u64>, n: u32) -> u64 {
   |               ------------------ help: consider changing this to be a mutable reference: `&mut std::collections::HashMap<u32, u64>`
...
20 |         map.insert(n, m);
   |         ^^^ `map` is a `&` reference, so the data it refers to cannot be borrowed as mutable

Can I use this approach in Rust? What would be the best solution to this problem?

Upvotes: 5

Views: 1425

Answers (2)

bitbangs
bitbangs

Reputation: 514

The trick is making map a mutable reference in the parameter list (and using lifetimes explicitly):

use std::collections::HashMap;

fn fib<'a>(n: u32, memo: &'a mut HashMap<u32, u32>) -> u32 {
    if n <= 2 {
        return 1;
    }

    return match memo.get(&n) {
        Some(&sum) => sum,
        None => {
            let new_fib_sum = fib(n - 1, memo) + fib(n - 2, memo);
            memo.insert(n, new_fib_sum);
            new_fib_sum
        }
    };
}

fn main() {
    let mut memo: HashMap<u32, u32> = HashMap::new();
    let n = 10; //or user input...or whatever
    print!("{}", fib(n, &mut memo));
}

Upvotes: 2

oli_obk
oli_obk

Reputation: 31273

You declared the map argument to f as &HashMap<u32, u64>, which is an immutable reference that only allows you to call get and other functions that do not modify the HashMap. Use &mut HashMap<u32, u64> as the type of map to require a reference that allows mutation. This also requires you to annotate the call site with &mut map instead of &map.

Personally I'd use a different approach using ownership transfer instead of references. But everyone has their own style.

pub fn fib_hash(n: u32) -> u64 {
    // This is the engine which recurses saving each value in the map
    fn f(map: HashMap<u32, u64>, n: u32) -> (HashMap<u32, u64>, u64) {
        if let Some(&number) = map.get(&n) {
            return (map, number);
        }
        let (map, a) = f(map, n - 1);
        let (mut map, b) = f(map, n - 2);
        let res = a + b;
        map.insert(n, res);
        (map, res)
    }
    let mut map = HashMap::new();
    map.insert(0, 0);
    map.insert(1, 1);
    map.insert(2, 1);
    f(map, n).1
}

Playground

Upvotes: 9

Related Questions