9.2. Memo: Fast memo functions

The Memo library provides fast polymorphic memo functions using hash tables. The interface is:

memo :: (a -> b) -> a -> b

So, for example, memo f is a version of f that caches the results of previous calls.

The searching is very fast, being based on pointer equality. One consequence of this is that the caching will only be effective if exactly the same argument is passed again to the memoised function. This means not just a copy of a previous argument, but the same instance. It's not useful to memoise integer functions using this interface, because integers are generally copied a lot and two instances of '27' are unlikely to refer to the same object.

This memoisation library works well when the keys are large (or even infinite).

The memo table implementation uses weak pointers and stable names (see the GHC/Hugs library document) to avoid space leaks and allow hashing for arbitrary Haskell objects. NOTE: while individual memo table entries will be garbage collected if the associated key becomes garbage, the memo table itself will not be collected if the function becomes garbage. We plan to fix this in a future version.

There's another version of memo if you want to explicitly give a size for the hash table (the default size is 1001 buckets):

memo_sized :: Int -> (a -> b) -> a -> b