通用的 memoize 模块怎样实现?

tiye · 2024 年9 月 24 日 03:36

memoize 函数是常用功能, 我找了点其他语言做参考

Rust 跟 Moonbit 相似度较高, 但 Rust 为了处理不同类型的数据的缓存, 用了 macro 自己去读 token 了. Moonbit 没有 macro, 应该抄不了,

dermesser/memoize/blob/master/inner/src/lib.rs#L272


      
          *
          * You can also specify a custom hasher: `#[memoize(CustomHasher: ahash::HashMap)]`, as some hashers don't use a `new()` method to initialize them, you can also specifiy a `HasherInit` parameter, like this: `#[memoize(CustomHasher: FxHashMap, HasherInit: FxHashMap::default())]`, so it will initialize your `FxHashMap` with `FxHashMap::default()` insteado of `FxHashMap::new()`
          *
          * This mechanism can, in principle, be extended (in the source code) to any other cache mechanism.
          *
          * `memoized_flush_<function name>()` allows you to clear the underlying memoization cache of a
          * function. This function is generated with the same visibility as the memoized function.
          *
          */
          #[proc_macro_attribute]
          pub fn memoize(attr: TokenStream, item: TokenStream) -> TokenStream {
             let func = parse_macro_input!(item as ItemFn);
             let sig = &func.sig;
          
             let fn_name = &sig.ident.to_string();
             let renamed_name = format!("memoized_original_{}", fn_name);
             let flush_name = syn::Ident::new(format!("memoized_flush_{}", fn_name).as_str(), sig.span());
             let map_name = format!("memoized_mapping_{}", fn_name);
          
             if let Some(syn::FnArg::Receiver(_)) = sig.inputs.first() {
                 return quote::quote! { compile_error!("Cannot memoize methods!"); }.into();

JavaScript 动态类型实际没有限制, 但也有一些对象不方便实现 Eq 的问题, 用了高阶函数暴露参数处理, 类型方面… 只看到 as… 看上去也不是适合 Moonbit 的方案,

github.com

sindresorhus/memoize/blob/main/index.ts#L123


      
          		if (maxAge > maxSetIntervalValue) {
          			throw new TypeError(`The \`maxAge\` option cannot exceed ${maxSetIntervalValue}.`);
          		}
          
          		if (maxAge < 0) {
          			throw new TypeError('The `maxAge` option should not be a negative number.');
          		}
          	}
          
          	const memoized = function (this: any, ...arguments_: Parameters<FunctionToMemoize>): ReturnType<FunctionToMemoize> {
          		const key = cacheKey ? cacheKey(arguments_) : arguments_[0] as CacheKeyType;
          
          		const cacheItem = cache.get(key);
          		if (cacheItem) {
          			return cacheItem.data;
          		}
          
          		const result = function_.apply(this, arguments_) as ReturnType<FunctionToMemoize>;
          
          		cache.set(key, {
          			data: result,

OCaml 的例子找到一个, 不大熟悉, 但看上去不是通用的,

https://cs3110.github.io/textbook/chapters/ds/memoization.html#memoization-using-higher-order-functions

功能上的话, 想要一个通用的 memoize, 如果有一定的定制空间对参数自行做筛选也更好, 想看看有没有同学有实现过, 想抄个用…

hackwaly · 2024 年9 月 26 日 13:33

pub fn memorized[K : Hash + Eq, V](f: (K) -> V) -> (K) -> V {
  let map = @hashmap.new()
  fn (k: K) -> V {
    match map[k] {
      Some(v) => v
      None => {
        let v = f(k)
        map[k] = v
        v
      }
    }
  }
}

pub fn memorized2[K1: Hash + Eq, K2 : Hash + Eq, V](f: (K1, K2) -> V) -> (K1, K2) -> V {
  let map = @hashmap.new()
  fn (k1: K1, k2: K2) -> V {
    match map[(k1, k2)] {
      Some(v) => v
      None => {
        let v = f(k1, k2)
        map[(k1, k2)] = v
        v
      }
    }
  }
}

tiye · 2024 年9 月 27 日 07:02

看上去暂时不能像 macro 或者动态语言那些完全单个 memoize 来处理所有场景了. 暂时这样写还是能先用着的, 感谢.