apfelmus apfelmus at quantentunnel.de
Sun May 27 06:02:53 EDT 2007

```Mark Engelberg wrote:
> I'd like to write a memoization utility.  Ideally, it would look
> something like this:
>
> memoize :: (a->b) -> (a->b)
>
> memoize f gives you back a function that maintains a cache of
> previously computed values, so that subsequent calls with the same
> input will be faster.

Note that due to parametricity, any function of this type is necessarily
either id or _|_. In other words, there are only two functions of type

∀a∀b. (a->b) -> (a->b)

That's because the functions has to work for all types a and b in the
same way, i.e. it may not even inspect how the given types a or b look
like. You need type classes to get a reasonable type for the function
you want

memoize :: Memoizable a => (a->b) -> (a->b)

Now, how to implement something like this? Of course, one needs a finite
map that stores values b for keys of type a. It turns out that such a
map can be constructed recursively based on the structure of a:

Map ()            b  := b
Map (Either a a') b  := (Map a b, Map a' b)
Map (a,a')        b  := Map a (Map a' b)

Here,  Map a b  is the type of a finite map from keys a to values b. Its
construction is based on the following laws for functions

() -> b  =~=  b
(a + a') -> b  =~=  (a -> b) x (a' -> b) -- = case analysis
(a x a') -> b  =~=  a -> (a' -> b)       -- = currying

For further and detailed explanations, see

R. Hinze. Memo functions, polytypically!
http://www.informatik.uni-bonn.de/~ralf/publications.html#P11

and

R. Hinze. Generalizing generalized tries.
http://www.informatik.uni-bonn.de/~ralf/publications.html#J4

Regards,
apfelmus

```