60

Creating a Type-Safe, Generic Memoization Utility

Thursday, November 12, 2020

Was working a bit through an article on memoization of pure functions today and had the idea to hack at a generic memoization utility that would take some given pure function, and optionally a function by which to serialize the arguments of the function.

I hacked at it some this evening and came up with this:

Code Examples

memoize.ts

type MemoizeableFunction = (...props: any[]) => any;

export function memoize<T extends MemoizeableFunction>(
  fn: MemoizeableFunction,
  serializeArgumentsFn: (...args: Parameters<T>) => string =
    (...args: Parameters<T>) => JSON.stringify(args)
): T {
  const cache: { [index: string]: ReturnType<T> } = {};
  const memoizedFn = (...args: Parameters<T>) => {
    const index = serializeArgumentsFn(...args);
    if (cache[index] === undefined) {
      cache[index] = fn(...args);
    }
    return cache[index];
  };
  return memoizedFn as T;
}

usage.ts

import { memoize } from 'memoize';

function sum(...args: number[]): number {
  return args.reduce((acc, n) => acc + n, 0);
}

// silly example - sorting is more performance intensive than
// the actual sum, but imagining the sum was computationally
// expensive, something like this could be a welcome optimization!
function serializeSumArgs(...args: number[]): string {
  return [...args].sort().join('|');
}

const memoizedSum = memoize(sum, serializeSumArgs);

memoizedSum(1, 2, 3, 4, 5, 6, 7, 8);
// Cache Miss!

memoizedSum(2, 1, 4, 5, 3, 8, 6, 7);
// Cache Hit!
Zack DeRose

Discussions are healthy ❤️

KA
Kajetan ·

How about this? This would be the way to infer type of arguments of the memoized function and its return type. See that the memoizedSum would be now inferring correct type (that of the sum function). Also the serializeSumArgs function will have to match sum in terms of type of inputs when both are passed to the memoize :)

type MemoizeableFunction<P, R> = (...props: P[]) => R;

export function memoize<P, R>(
  fn: MemoizeableFunction<P, R>,
  serializeArgumentsFn: (...args: P[]) => string =
    (...args: P[]) => JSON.stringify(args)
): MemoizeableFunction<P, R> {
  const cache: { [index: string]: ReturnType<MemoizeableFunction<P, R>> } = {};
  const memoizedFn = (...args: P[]) => {
    const index = serializeArgumentsFn(...args);
    if (cache[index] === undefined) {
      cache[index] = fn(...args);
    }
    return cache[index];
  };
  return memoizedFn;
}
KA
Kajetan ·

Also, I jsut realized that ReturnType<MemoizeableFunction<P, R>> can be simplified to just R ;)