## Memoizing polymorphic functions – part two

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