Rust closure to be called on a cache miss

Question

The official Rust book chapter 13.1 includes an exercise to expand on the example provided in the chapter:

Try modifying Cacher to hold a hash map rather than a single value. The keys of the hash map will be the arg values that are passed in, and the values of the hash map will be the result of calling the closure on that key. Instead of looking at whether self.value directly has a Some or a None value, the value function will look up the arg in the hash map and return the value if it’s present. If it’s not present, the Cacher will call the closure and save the resulting value in the hash map associated with its arg value.

The second problem with the current Cacher implementation is that it only accepts closures that take one parameter of type u32 and return a u32. We might want to cache the results of closures that take a string slice and return usize values, for example. To fix this issue, try introducing more generic parameters to increase the flexibility of the Cacher functionality.

The following is what I have:

use std::thread;
use std::time::Duration;
use std::collections::HashMap;
use std::hash::Hash;

struct Cacher<T, K, J>
    where T: Fn(&K) -> J,
    K: Hash + Eq,
    J: Clone
{
    calculation: T,
    value: HashMap<K, J>,
}

impl<T, K, J> Cacher<T, K, J>
    where T: Fn(&K) -> J,
    K: Hash + Eq,
    J: Clone
{
    fn new(calculation: T) -> Cacher<T, K, J> {
        Cacher {
            calculation,
            value: HashMap::new(),
        }
    }

    fn value(&mut self, arg: K) -> J {
        if let Some(v) = self.value.get(&arg) {
            v.clone()
        } else {
            let v = (self.calculation)(&arg);
            self.value.insert(arg, v.clone());
            v
        }
    }
}

fn generate_workout(intensity: u32, random_number: u32) {
    let mut expensive_result = Cacher::new(|&num| {
        println!("calculating slowly...");
        thread::sleep(Duration::from_secs(2));
        num
    });

    if intensity < 25 {
        println!(
            "Today, do {} pushups!",
            expensive_result.value(&intensity)
        );
        println!(
            "Next, do {} situps!",
            expensive_result.value(&intensity)
        );
    } else {
        if random_number == 3 {
            println!("Take a break today! Remember to stay hydrated!");
        } else {
            println!(
                "Today, run for {} minutes!",
                expensive_result.value(&intensity)
            )
        }
    }
}

fn main() {
    let simulated_user_specified_value = 10;
    let simulated_random_number = 7;

    generate_workout(
        simulated_user_specified_value,
        simulated_random_number
    );
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn call_with_different_values() {
        let mut c = Cacher::new(|&a| a);

        let v1 = c.value(1);
        let v2 = c.value(2);
        assert_eq!(v1, 1);
        assert_eq!(v2, 2);

        let mut d = Cacher::new (|a: &String| a.len());
        let str1 = String::from("abc");
        let v3 = d.value(str1);
        assert_eq!(v3, 3);
    }
}

I don't like the fact that my approach has the generic parameter J bounded by Clone trait. How can I make this work without the bound?

Any other feedback is appreciated.

Answer 1

I like what you've done! I don't have too many comments about the content of it, since it looks good. However, you'll see below that I changed the field name value to cache and some of the generic parameter names, just to make things a little clearer. This is just a subjective preference, but I used F for function, K for key, and V for value.

Another thing to note is that in many cases, you don't need to put trait bounds on the parameters for the struct itself. You just need the bounds when you are implementing functions with it, and having the bounds on the struct doesn't save you from having to write the bounds when you use it as a parameter.

If you want to get rid of the Clone bound, you can return a reference to the value now stored within the cache. Here's one possible implementation of that, using HashMap's entry API.

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

struct Cacher<F, K, V> {
    calculation: F,
    cache: HashMap<K, V>,
}

impl<F, K, V> Cacher<F, K, V>
where
    F: Fn(&K) -> V,
    K: Hash + Eq,
{
    fn new(calculation: F) -> Self {
        Cacher {
            calculation,
            cache: HashMap::new(),
        }
    }

    fn value(&mut self, arg: K) -> &V {
        use std::collections::hash_map::Entry;

        match self.cache.entry(arg) {
            Entry::Occupied(occupied) => occupied.into_mut(),
            Entry::Vacant(vacant) => {
                let value = (self.calculation)(vacant.key());
                vacant.insert(value)
            }
        }
    }
}