Why cant a static hashmap for a memoizing function be borrowed as mutable?

Question

I'm trying to create a memoization function in Rust. The problem comes when getting a mutable reference for the cache HashMap. I'm not still confident with the type system and I'm struggling a bit.

use std::collections::HashMap;
use std::hash::Hash;

fn memoize<A, B, F>(f: F, cache: &'static HashMap<A, B>) -> impl Fn(A) -> B
where
    A: Eq + Hash + Copy,
    B: Clone,
    F: Fn(A) -> B,
{
    move |value: A| {
        if !cache.contains_key(&value) {
            cache.insert(value, f(value.clone()));
        }
        let res = cache.get(&value).unwrap();
        res.clone()
    }
}

The error is:

error[E0596]: cannot borrow immutable borrowed content `**cache` as mutable
  --> src/lib.rs:12:13
   |
12 |             cache.insert(value, f(value.clone()));
   |             ^^^^^ cannot borrow as mutable

Why cannot a static lifetime parameter be mutable?

Answer 1

A variable is immutable by default in Rust, therefore you cannot mutate a variable that is not declared as mut. The 'static lifetime does not influence the mutability, but only how long the variable lives.

A Fn "[...] can be called repeatedly without mutating state.". And exactly here is the problem. You want to mutate the environment (in this case your HashMap).

You have to use a FnMut to be able to mutate the environment.

If you use the Entry API, you can simplify your code:

use std::collections::HashMap;
use std::hash::Hash;

fn memoize<A, B, F>(f: F, cache: &'static mut HashMap<A, B>) -> impl FnMut(A) -> B
where
    A: Eq + Hash + Copy,
    B: Clone,
    F: Fn(A) -> B,
{
    move |value: A| {
        let res = cache.entry(value).or_insert_with(|| f(value));
        res.clone()
    }
}

As a sidenote, if you compile your code with #[feature(nll)] the error message is actually very good.

error[E0596]: cannot borrow `*cache` as mutable, as `Fn` closures cannot mutate their captured variables
  --> src/lib.rs:14:13
   |
14 |             cache.insert(value, f(value.clone()));
   |             ^^^^^ cannot borrow as mutable
   |
help: consider changing this to accept closures that implement `FnMut`