## Memoizing polymorphic functions – part one

Memoization takes a function and gives back a semantically equivalent function that reuses rather than recomputes when applied to the same argument more than once. Variations include not-quite-equivalence due to added strictness, and replacing value equality with pointer equality.

Memoization is often packaged up polymorphically:

```
memo :: (???) => (k -> v) -> (k -> v)
```

For pointer-based (“lazy”) memoization, the type constraint (“???”) is empty.
For equality-based memoization, we’d need at least `Eq k`

, and probably `Ord k`

or `HasTrie k`

for efficient lookup (in a finite map or a possibly infinite memo trie).

Although `memo`

is polymorphic, its argument is a *monomorphic* function.
Implementations that use maps or tries exploit that monomorphism in that they use a type like `Map k v`

or `Trie k v`

.
Each map or trie is built around a particular (monomorphic) type of keys.
That is, a single map or trie does not mix keys of different types.

Now I find myself wanting to memoize *polymorphic* functions, and I don’t know how to do it.

Continue reading ‘Memoizing polymorphic functions – part one’ »