[Haskell-cafe] Re: Memoization

[apfelmus]

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