Part one of this series introduced the problem of memoizing functions involving polymorphic recursion.
The caching data structures used in memoization typically handle only one type of argument at a time.
For instance, one can have finite maps of differing types, but each concrete finite map holds just one type of key and one type of value.
I extended memoization to handle polymorphic recursion by using an existential type together with a reified type of types.
This extension works (afaik), but it is restricted to a particular form for the type of the polymorphic function being memoized, namely
-- Polymorphic function
type k :--> v = forall a. HasType a => k a -> v a
My motivating example is a GADT-based representation of typed lambda calculus, and some of the functions I want to memoize do not fit the pattern.
After writing part one, I fooled around and found that I could transform these awkwardly typed polymorphic functions into isomorphic form that does indeed fit the restricted pattern of polymorphic types I can handle.
Continue reading ‘Memoizing polymorphic functions – part two’ »
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.
Continue reading ‘Memoizing polymorphic functions – part one’ »