12th June 2009, 02:04 pm

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

: http://conal.net/blog/posts/memoizing-polymorphic-functions-part-one/ "Blog post"
: http://www.cse.chalmers.se/~rjmh/Papers/hughes_85_lazy.pdf "Paper by John Hughes"
: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.1948 "Paper by Simon Peyton Jones, Simon Marlow, and Conal Elliott"
: http://conal.net/blog/posts/elegant-memoization-with-functional-memo-tries/ "blog post"
of this series introduced ...

10th June 2009, 04:36 pm

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

: http://www.cse.chalmers.se/~rjmh/Papers/hughes_85_lazy.pdf "Paper by John Hughes"
: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.1948 "Paper by Simon Peyton Jones, Simon Marlow, and Conal Elliott"
: http://conal.net/blog/posts/elegant-memoization-with-functional-memo-tries/ "blog post"
Memoization takes a function and gives back a semantically equivalent function that reuses rather than recomputes when applied to ...