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