Mdthbs

Let’s say fn(x) is a pure function that does something expensive, like returning a list of the prime factors of x.

And let’s say we make a memoized version of the same function called memoizedFn(x). It always returns the same result for a given input, but it maintains a private cache of previous results to improve performance.

Formally speaking, is memoizedFn(x) considered pure?

Or is there some other name or qualifying term used to refer to such a function in FP discussions? (i.e. a function with side effects that may affect the computational complexity of subsequent calls but that may not affect the return values.)

Yes. The memoized version of a pure function is also a pure function.

All that function purity cares about is the effect that input parameters on the return value of the function (passing the same input should always produce the same output) and any side effects relevant to global states (e.g. text to the terminal or UI or network). Computation time and extra memory usages is irrelevant to function purity.

Caches of a pure function is pretty much invisible to the program, a functional programming language is allowed to automatically optimise a pure function to a memoized version of the function if it can determine that it'll be beneficial to do so. In practice, automatically determining when memoization is beneficial is actually quite a difficult problem, but such optimisation would be valid.

Wikipedia defines a "Pure Function" as a function that has the following properties:

• Its return value is the same for the same arguments (no variation with local static variables, non-local variables, mutable reference arguments or input streams from I/O devices).




• Its evaluation has no side effects (no mutation of local static variables, non-local variables, mutable reference arguments or I/O streams).

In effect, a pure function returns the same output given the same input, and doesn't affect anything else outside of the function. For purposes of purity, it doesn't matter how the function computes its return value, so long as it returns the same output given the same input.

Functionally pure languages like Haskell routinely use memoization to speed up a function by caching its previously computed results.

It depends on how you do it.

Usually people want to memoize by mutating some sort of cache dictionary. This has all the problems associated with impure mutation, such as having to worry about concurrency, worrying about the cache growing too large, etc.

However, you can memoize without impure memory mutation. One example is in this answer, where I track the memoized values externally by means of a lengths argument.

In the link Robert Harvey provided, lazy evaluation is used to avoid side effects.

Another technique sometimes seen is to explicitly mark the memoization as an impure side effect in the context of an IO type, such as with cats-effect's memoize function.

This last one brings up the point that sometimes the goal is just encapsulating mutation rather than eliminating it. Most functional programmers consider it "pure enough" to make impurity explicit and encapsulated.

If you want a term to differentiate it from a truly pure function, I think it's sufficient to just say "memoized with a mutable dictionary." That lets people know how to use it safely.