Memoizing a function

code review
1

I am working my way through Category Theory for Programmers, and came up with the following code to memoize a function:

use std::{collections::HashMap, hash::Hash};

fn memoize<A, B, F>(f: F) -> impl FnMut(A) -> B
where
    A: Eq + Hash + Clone,
    B: Clone,
    F: Fn(A) -> B,
{
    let mut cache = HashMap::new();
    move |x| (*cache.entry(x.clone()).or_insert_with(|| f(x))).clone()
}

I have a two questions:

  • Why can I not use or_insert instead of or_insert_with? If I do, then the results are not cached properly.
  • Should I make the trait bounds for A and B Copy? It simplifies the code by removing the clone calls, but I'm not sure if it makes sense semantically.
2

In that case, there is nothing that prevents f(x) from being evaluated every time regardless of whether the cache has an entry or not. or_insert() just discards the value you pass if there is already an entry. It does not and cannot control evaluation of the expression f(x), whereas or_insert_with() can decide not to call the || f(x) closure you pass, and f(x) is only evaluated if the closure is called.

Switching to a Copy bound does nothing but make your function applicable to fewer types. Everything that implements Copy also implements Clone, so if you can write your function with Clone then you should.

4 Likes
3

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.