[Haskell-cafe] Re: Memoization
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
More information about the Haskell-Cafe
mailing list