memo

Memoization tools, TC39 proposal-function-memo implementation.

Install

deno.land:

import * as mod from "https://deno.land/x/memoization@$VERSION/mod.ts";

npm:

npm i @miyauci/memo

Usage

Returns the proxy function whose call is monitored. It calls at most once for each given arguments.

import { memo } from "https://deno.land/x/memoization@$VERSION/mod.ts";

function f(x: number): number {
  console.log(x);
  return x * 2;
}

const fMemo = memo(f);
fMemo(3); // Prints 3 and returns 6.
fMemo(3); // Does not print anything. Returns 6.
fMemo(2); // Prints 2 and returns 4.
fMemo(2); // Does not print anything. Returns 4.
fMemo(3); // Does not print anything. Returns 6.

Either version would work with recursive functions:

import { memo } from "https://deno.land/x/memoization@$VERSION/mod.ts";

const fib = memo((num: number): number => {
  if (num < 2) return num;

  return fib(num - 1) + fib(num - 2);
});

fib(1000);

Custom cache

To control the cache, specify cache.

The cache must implement the following interfaces:

interface MapLike<K, V> {
  get(key: K): V | undefined;
  has(key: K): boolean;
  set(key: K, value: V): void;
}

By default, an unlimited cache is used by WeakMap.

import {
  type MapLike,
  memo,
} from "https://deno.land/x/memoization@$VERSION/mod.ts";

declare const lruCache: MapLike<object, unknown>;
declare const fn: () => unknown;

const $fn = memo(fn, lruCache);

Keying

Cache keys are represented by composite keys.

The composite keys are passed several elements for the key, called components.

The components are as follows:

• target function
• this arg(this)
• new target(new.target)
• args

Of these, target function is used to identify a unique function. The target function is not used to identify a unique function, since the composite key is a global registry. For more information, see FAQ: What scope is the idempotentcy?

Also, composite key employs the same-value-zero algorithm to verify the equivalence of each component.

You can modify the args component through the keying callback.

import {
  type MapLike,
  memo,
} from "https://deno.land/x/memoization@$VERSION/mod.ts";

declare const respond: (request: Request) => Response;

const $respond = memo(
  respond,
  undefined,
  ([request]) => [request.method, request.url],
);

Currently, only the args component can be modified. This is being discussed in #4 (comment) and it is not clear how this arg and new target should be handled.

Instantiation caching

Caching of instantiation is also supported. Calls to constructor functions with the new operator are cacheable based on their arguments.

import { memo } from "https://deno.land/x/memoization@$VERSION/mod.ts";
import { assert } from "https://deno.land/std/testing/asserts.ts";

assert(new Error() !== new Error());

const $Error = memo(Error);

assert(new $Error() === new $Error());
assert($Error("test") === $Error("test"));

assert(new $Error() !== $Error());
assert(new $Error() !== new $Error("test"));

Polyfill

Polyfill affects the global object. You must be very careful when using it.

import "https://deno.land/x/memoization@$VERSION/polyfill.ts";

const fib = ((num: number): number => {
  if (num < 2) return num;

  return fib(num - 1) + fib(num - 2);
}).memo();

fib(1000);

API

See deno doc for all APIs.

Contributing

See CONTRIBUTING.md

License

MIT © 2023 Tomoki Miyauchi