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).
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.