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’ »