Pfthb

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,
 
 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?

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,
 
 let res = cache.entry(value).or_insert_with(

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`