[Haskell-cafe] Memoization

Mark Engelberg mark.engelberg at gmail.com
Sat May 26 22:34:32 EDT 2007


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.

I've searched the web for memoization examples in Haskell, and all the
examples use the trick of storing cached values in a lazy list.  This
only works for certain types of functions, and I'm looking for a more
general solution.

In other languages, one would maintain the cache in some sort of
mutable map.  Even better, in many languages you can "rebind" the name
of the function to the memoized version, so recursive functions can be
memoized without altering the body of the function.

I don't see any elegant way to do this in Haskell, and I'm doubting
its possible.  Can someone prove me wrong?

--Mark


More information about the Haskell-Cafe mailing list