3
votes

In chapter 13 of the Rust book you implement a Cacher struct for lazy initialization to demonstrate the use of Closures and Functional Programming. As an exercise they encourage the reader to try and create a generic Cacher which can store more than one value. To do so they recommend using a Hashmap.

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.

To solve this exercise I used the following code:

struct Cacher<T, K, V>
    where T: Fn(K) -> V
{
    calculation: T,
    values: HashMap<K, V>,
}

impl<T, K, V> Cacher<T, K, V>
    where T: Fn(K) -> V,
          K: std::cmp::Eq + std::hash::Hash + Clone,
{
    fn new(calculation: T) -> Cacher<T, K, V> {
        Cacher {
            calculation,
            values: HashMap::new(),
        }
    }

    fn value(&mut self, intensity: K) -> &V {
        self.values.entry(intensity.clone()).or_insert((self.calculation)(intensity))
    }
}

This code compiles and runs, but doesn't serve as a proper Cacher due to the fact that (self.calculation)(intensity) is always executed. Even when the entry exists. What I understand from documentation and examples is that the Entry::or_insert function is only executed if the Entry doesn't exist.

I am aware of the solution to the exercise from question Is it possible to use a single generic for both key and value of a HashMap?, but I would like to know if it's possible to solve the problem the way I'm currently doing it.

Edit: As explained in a comment: or_insert_with does not solve the problem. When trying or_insert_with(|| (self.calculation)(intensity.clone())) I get the following error error[E0502]: cannot borrow self as immutable because it is also borrowed as mutable.

1
TL;DR: have you tried or_insert_with instead?justinas
I have just tried or_insert_with(|| (self.calculation)(intensity.clone())) and get the following error: error[E0502]: cannot borrow `self` as immutable because it is also borrowed as mutable. Is there any difference between or_insert and or_insert_with besides the fact that the former expects a value and the latter expects a closure that returns a value?theHoatzin
Hum, that's true, you cannot do that like this.Boiethios
You just need to store a reference to calculation in a separate let statement in the line before: let calculation = &self.calculation;. The borrow checker is smart enough to see that self.calculation and self.values don't overlap if they occur in the same scope, but if you just use self.calculation inside the closure, it will trigger a borrow of all of self, which does overlap with self.values.Sven Marnach
@SvenMarnach Thank you very much. The solution was adding the line you mentioned and using @justinas suggestion to use or_insert_with.theHoatzin

1 Answers

12
votes

The problem with your code is that function arguments are always evaluated before calling the function in Rust (and most imperative languages). This means before or_insert() is even called, the code will unconditionally call (self.calculation)(intensity). The or_insert() function will internally check whether a value was already present in the entry and only insert the new one it gets passed as an argument if there is none, but this happens only after self.calculation was already called.

This problem can be solved by using the or_insert_with() method. This method accepts a closure instead of a value, and only calls the closure if it needs to insert a value. Here is the full code:

use std::collections::HashMap;

struct Cacher<T, K, V> {
    calculation: T,
    values: HashMap<K, V>,
}

impl<T, K, V> Cacher<T, K, V>
where
    K: std::cmp::Eq + std::hash::Hash + Clone,
{
    fn new(calculation: T) -> Cacher<T, K, V> {
        Cacher {
            calculation,
            values: HashMap::new(),
        }
    }

    fn value(&mut self, intensity: K) -> &V
    where
        T: Fn(K) -> V,
    {
        let calculation = &self.calculation;
        self.values
            .entry(intensity.clone())
            .or_insert_with(|| calculation(intensity))
    }
}

One subltety in the implementation of value() is that you need to store a reference to self.calculation in a separate variable. Otherwise the closure would trigger a borrow of self, which overlaps with the mutable borrow of self.values triggered by the call to self.values.entry(). If you explicitly borrow only self.calculation in the outer scope, the borrow checker is smart enough to figure out that it does not overlap with self.values.

As a side note, I recommend using rustfmt for consistent code formatting. I also recommend scoping trait bounds as narrowly as possible, to avoid unnecessary duplication. Both these recommendations are included in the code above.