Is it possible to use a single generic for both key and value of a HashMap?

Question

In chapter 13 of the Rust book, you implement a Cacher to use memoization to demonstrate functional programming and how to speed up long-running tasks. As an extra challenge, they recommend making the Cacher allow multiple keys using a HashMap and also leveraging generics to allow more flexibility.

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.

I was able to implement the HashMap, however when trying to replace the closure definition u32 with a generic type and use that as the signature of the HashMap, I run into an issue.

use std::collections::hash_map::Entry;
use std::collections::HashMap;
use std::thread;
use std::time::Duration;

struct Cacher<'a, T>
where
    T: Fn(&'a u32) -> &'a u32,
{
    calculation: T,
    values: HashMap<&'a u32, &'a u32>,
}

impl<'a, T> Cacher<'a, T>
where
    T: Fn(&'a u32) -> &'a u32,
{
    fn new(calculation: T) -> Cacher<'a, T> {
        Cacher {
            calculation,
            values: HashMap::new(),
        }
    }

    fn values(&mut self, arg: &'a u32) -> &'a u32 {
        match self.values.entry(arg) {
            Entry::Occupied(e) => &*e.into_mut(),
            Entry::Vacant(e) => &*e.insert(&(self.calculation)(&arg)),
        }
    }
}

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.values(&intensity));
        println!("Next, do {} situps!", expensive_result.values(&intensity));
    } else {
        if random_number == 3 {
            println!("Take a break today! Remember to stay hydrated!");
        } else {
            println!(
                "Today, run for {} minutes!",
                expensive_result.values(&intensity)
            );
        }
    }
}

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

    generate_workout(simulated_user_specified_value, simulated_random_number);
}

I tried K, V generics as below and it complains with Expected one of 7 possible values here pointing to the first type definition.

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

struct Cacher<'a, T: 'a, K: 'a, V: 'a>
where
    T: Fn(&'a K) -> &'a V,
    K: Hash + Eq,
{
    calculation: T,
    values: HashMap<&'a K, &'a V>,
}

impl<'a, T: 'a, K: 'a, V: 'a> Cacher<'a, T: 'a, K: 'a, V: 'a>
where
    T: Fn(&'a K) -> &'a V,
    K: Hash + Eq,
{
    fn new(calculation: T) -> Cacher<'a, T: 'a, K: 'a, V: 'a> {
        Cacher {
            calculation,
            values: HashMap::new(),
        }
    }

    fn values(&mut self, arg: &'a K) -> &'a V {
        match self.values.entry(arg) {
            Entry::Occupied(e) => &*e.into_mut(),
            Entry::Vacant(e) => &*e.insert(&(self.calculation)(&arg)),
        }
    }
}

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.values(&intensity));
        println!("Next, do {} situps!", expensive_result.values(&intensity));
    } else {
        if random_number == 3 {
            println!("Take a break today! Remember to stay hydrated!");
        } else {
            println!(
                "Today, run for {} minutes!",
                expensive_result.values(&intensity)
            );
        }
    }
}

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

    generate_workout(simulated_user_specified_value, simulated_random_number);
}

Results in the following error:

error: expected one of `!`, `(`, `+`, `,`, `::`, `<`, or `>`, found `:`
  --> src/main.rs:16:39
   |
16 | impl<'a, T: 'a, K: 'a, V: 'a> Cacher<T: 'a, K: 'a, V: 'a>
   |                                       ^ expected one of 7 possible tokens here

Is the only way to add 2 more generics (i.e. K, V) or is there a way to reuse a single generic? If 2 required, what am I missing above?

Is there a more idiomatic approach to solving this problem? The Rust book does not offer a solution, unfortunately.

Answer 1

Your implementation does not compile because lifetime bounds have to be declared only after impl:

impl<'a, T: 'a, K: 'a, V: 'a> Cacher<'a, T, K, V>
where
    T: Fn(&'a K) -> &'a V,
    K: Hash + Eq,
{
    fn new(calculation: T) -> Cacher<'a, T, K, V> {
        Cacher {
            calculation,
            values: HashMap::new(),
        }
    }
}

Storing references into the HashMap implies that you have to manage lifetimes and assure that the values referenced by HashMap outlive the Cacher.

Another approach to consider may be to cache by values:

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

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

    fn value(& mut self, arg: K) -> &V {    
        match self.value.entry(arg.clone()) {
            Entry::Occupied(v) => v.into_mut(),
            Entry::Vacant(v) =>   v.insert((self.calculation)(arg)),
        }
    }
}

Please note that in this solution I added the constraint that K is Clone

Answer 2

This question's pretty old, but I found this question while browsing online to see if my solution was "correct." I'll share it here, as it's slightly different that the accepted answer, and maintains the original signature for the value method in the book:

struct Cacher<T, K, V>
    where T: Fn(K) -> V,
          K: Eq + Hash + Copy,
          V: Copy {
    calculation: T,
    cache: HashMap<K, V>,
}

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

    fn value(&mut self, arg: K) -> V {
        match self.cache.get(&arg) {
            Some(&v) => v,
            None => {
                let v = (self.calculation)(arg);
                self.cache.insert(arg, v);
                v
            }
        }
    }
}

Here I have explicit generic parameters for the key and value of the HashMap that will cache values for Cacher. K has trait bounds for Eq, Hash, and Copy, and V only needs the Copy trait bound.