How can memoize be implemented in pure functional languages?

Question

One advantage of pure functions is that their inputs fully determine their outputs, allowing the result to be cached for later use. However, I don't see how this can be implemented without either:

• mutable global state to store a cache (not possible in a truly pure functional language)
• threading a cache through all computations (unwieldy, even with a monad)
• some kind of annotation with run-time support (a bit hacky, but probably sufficient)
• a very clever run-time (might be unpredictable and have other overheads)

How is memoize commonly implemented in pure functional languages?

Answer 1

I just struggled myself through optimizing some frequently recalculated computations in a pure functional style (though the language I'm using is actually not purely functional), so I figured I'd share my findings.

In a way, the answer is already in the question, as it lists all possible implementation approaches. Assuming that #1 is out of the question when using a purely functional language, options #2, #3, and #4 are all valid possibilities, and it depends a little on the context which option would be typically used.

For my particular problem (repeated re-calculation of type information), I opted for option #2 using a State monad, with the cache contents being the state that is being carried through. Luckily in my case, all functions/methods that needed caching had the same return type, so I replaced the original return type with the new state monad (which consisted of the original type and the cache). As you alluded, it turned out to be a pretty involved refactoring, but in the end the exterior interface did not look much different, except for the different return type.

I also considered option #3, i.e. by moving the problem into some kind of "meta-space" outside of the actual function execution, for example by using Aspect-Oriented Programming (AOP). I'm working in a JVM-based language so I had a good look at Spring's @Cacheable and other similar solutions like jcabi-aspects. Other languages have similar options, e.g. Python's @cached_property. It's a pretty transparent way of adding caching without changing much else, but in my case this solution didn't interact well with some previous design choices I'd made (I'm already using a different dependency injection framework that makes use of AOP, and introducing a second DI solution would have been complicated).

Lastly, option #4 is something that one would find at the language implementation level. A purely functional programming language, could technically cache any function result using its respective input arguments as cache key. I am not aware of any programming language that does this automatically, but (manually) creating memoized functions is possible in common functional languages like Clojure and Haskell. Doing this automatically, is probably difficult as one would have to come up with a caching and cache eviction strategy that provides a reasonable trade-off between time and memory for many different use case scenarios.