返回一个返回引用的函数

Question

我想写一个简单的记忆化函数。

fn memoize<K: Eq + Hash, V: Clone>(mut func: impl FnMut(&K) -> V) -> impl FnMut(K) -> V {
  let mut cache = HashMap::new();
  |key| {
    cache
      .entry(key)
      .or_insert_with_key(|k| func(k))
      .clone()
  }
}

Eq + Hash 在参数上的限制似乎是合理的，但在返回值上使用 Clone 似乎是不必要的。理想情况下，函数签名应该如下：

fn memoize<K: Eq + Hash, V>(mut func: impl FnMut(&K) -> V) -> impl FnMut(K) -> &mut V

需要指定返回引用的生命周期（这很有意义）。

理想情况下，&mut V 应该存活的时间与函数的引用相同（或类似 &'a mut impl FnMut(K) -> &'a mut V 这样）。

由于 Fn traits 的实现不稳定，如果我想在 Fn traits 内部留下（而不是编写带有 fn call(&'a mut self，key: K) -> &'a mut V 的结构体），那么在稳定版的 Rust 中是否有方法可以实现？

- Link0

---

我不确定对于一个记忆化函数（通常是纯函数），返回&mut V是否有意义。为什么不使用&V呢？ - Thomas

继续通过引用而不是值获取&K可能也是有意义的，但这时你需要K: Clone。它可以让你避免在键已经存在于映射中的情况下进行克隆（这可能是常见情况）。 - Thomas

是的，我以前在使用输入API时遇到过这种限制，即使已经存在，它也会占用键的所有权。在这种情况下，我并不真的关心它。我想这会导致两次哈希或分配（如果无法移动键）的权衡。 - Link0

我不确定我理解你的意图，但是你可以将生命周期添加到返回的实现类型中。类似这样的代码 playground。 - rodrigo

问题实际上在于确保缓存被借用到返回的引用的生命周期，但由于缓存被捕获到环境中，Rust不允许返回的引用逃逸出现的FnMut。如果您改为使用显式结构，则可以正常工作，尽管使用方法比直接调用略微不太方便：playground。 - eggyal

Answer 1

很遗憾，这是不可能的。即使手动实现了 FnMut，除非我们将 Output 变成一个泛型关联类型，否则也不可能实现。

pub trait GatifiedFnMut<Args: std::marker::Tuple> {
    type Output<'a>
    where
        Self: 'a;
    extern "rust-call" fn call_mut(&mut self, args: Args) -> Self::Output<'_>;
}

pub struct Memoized<K, V, F> {
    cache: HashMap<K, V>,
    func: F,
}

impl<K: Eq + Hash, V, F: FnMut(&K) -> V> GatifiedFnMut<(K,)> for Memoized<K, V, F> {
    type Output<'a> = &'a mut V
    where
        Self: 'a;
    extern "rust-call" fn call_mut(&mut self, (key,): (K,)) -> Self::Output<'_> {
        self.cache.entry(key).or_insert_with_key(&mut self.func)
    }
}

（注：即使没有GATs，也可以解决这个问题，但是不能使用当前的FnOnce/FnMut/Fn特质，或者至少非常不方便，请参见下面链接的问题。）

更多信息可以在users.rust-lang.org找到。

- Chayim Friedman