General
The conceptual problem with memoized pure functions is that pure functions typically (in fact, normally by their mere definition) do not cause side effects, while memoization necessarily requires side effects (changes of state). What was meant was probably to construct a memoized anonymous (lambda) - functions - this is possible, because the latter can manipulate mutable state.
A note on pure functions and terminology
Somewhat as a side note, but a rather important one: in fact, the standard notion of pure function in Computer Science is exactly this - a function without side effects. It is important to emphasize (as suggested by WReach in comments), that Mathematica's notion of pure function is different - in Mathematica, pure function is any function built with the keyword Function
, regardless of whether or not the application of such function may cause side effects. It is an important distinction to keep in mind, particularly for those who come from other languages supporting pure functions (in the usual sense).
Speaking of side effects, their presence always means that the function manipulates some global state. While the essence is the same, this may take different forms:
Manipulating an external mutable state by using it implicitly in the body of the function
var = 1;
Function[var++]
Leaking internal state (Module
- generated variables and such), and manipulating that (applies to closures constructed using Module
or similar):
Module[{var = 1}, Function[var++]]
Mutating external variables, using (an emulation of) pass-by-reference semantics:
var=0;
Function[Null, #++,HoldFirst][var]
For the solution suggested below, we will be using the second version of side effects - the one relevant for mutable closures.
And once again, the functions constructed this way, are still called pure in Mathematica, but are not called pure elsewhere in the CS lore / literature.
The case at hand
In Mathematica, by pure function one usually means a function built with the Function
keyword (as opposed to functions which are essentially global rules), and as such, it can contain side effects. So, you can do something like this:
ff =
Module[{f = <||>},
Function[
If[KeyExistsQ[f, #],
f[#],
f[#] = If[# > 0, 1, 2]
]
]
]
(* If[KeyExistsQ[f$1407, #1], f$1407[#1], f$1407[#1] = If[#1 > 0, 1, 2]]& *)
which would effectively work similarly to a memoized function.
Automation
The process can be automated with the following constructor:
ClearAll[makeMemoPF];
SetAttributes[makeMemoPF, HoldFirst];
makeMemoPF[body_, start_: <||>] :=
Module[{fn = start},Function[If[KeyExistsQ[fn, #], fn[#], fn[#] = body]]]
where now you can simply write:
ff = makeMemoPF[If[# > 0, 1, 2]]
Advantages of this construct
One advantage I can see in this construct w.r.t. a usual memoized function is that, as with other functions based on Function
, you can pass this without storing in a variable. The good thing here is that then, once this function is no longer referenced, it will be automatically garbage-collected, and that would also be true for the inner variable f
, used to store the mutable state (memoized values).
Let me illustrate this aspect with the example of Fibonacci numbers. Suppose we just need to compute first 20 (say) of those, but use recursive function and take an advantage of memoization. We would write there:
Map[makeMemoPF[#0[# - 1] + #0[# - 2], <|0 -> 1, 1 -> 1|>], Range[20]]
(* {1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946} *)
and one can check that there were no leaks of inner variable we use for memoization, after this code executed - so it has been successfully garbage-collected (for those who are puzzled by #0
, this is the syntax used to call Function
recursively in Mathematica. More details can be found in the docs, and also e.g. here).
Extension: building controllable-size garbage-collectable caches
The technique above can also be extended in another interesting direction, where the standard memoization does not provide a simple solution: what if
we want to limit the size of the cache (that is, a collection of memoized values)? I will only consider a simpler case, when we limit the number of stored elements - while the case when we limit based on ByteCount
can be tackled too, but is more complex.
Here is the code that implements that. First, we need two auxilliary functions. The first one is a macro, to avoid using With
, when we need to execute some code after we obtain the result, before returning it:
ClearAll[withCodeAfter];
SetAttributes[withCodeAfter, HoldRest];
withCodeAfter[before_, after_] := (after; before);
The other function we need is one to shrink an association to a given size, dropping key-value pairs from the start:
ClearAll[assocShrink];
assocShrink[a_Association, size_] /; Length[a] > size := Drop[a, Length[a] - size];
assocShrink[a_Association, _] := a;
Finally, the constructor for the cache:
ClearAll[makeCachedPF];
SetAttributes[makeCachedPF, HoldFirst];
makeCachedPF[body_, start_: <||>, cacheLimit_: Infinity] :=
Module[{f = <||>},
Function[
If[KeyExistsQ[f, #],
f[#]
,
withCodeAfter[
f = assocShrink[f, cacheLimit];
f[#] = body
,
f = assocShrink[f, cacheLimit]
]
]]];
What this does is pretty simple: it uses the fact, that the new key-value pairs are added from the right to an association, when assignment is used. Then, every time we add a new key-value pair, we also remove the "oldest" one from the left, if the total number of values stored in a cache has exceeded a given limit. In this way, we keep the maximal number of cached values under control.
Let us see how this works, using an example: here is our data:
data = RandomInteger[{1000, 1100}, 10000];
which is, a large number of values from 1000
to 1100
. We now want to compute a function, that determines a total number of primes in Range[x]
, where x
is our data point, on this data.
Map[Total[Boole@PrimeQ@Range[#]]&,data]//Short//AbsoluteTiming
(* {6.59317,{169,183,172,180,183,180,179,172,181,176 <<9980>>,168,175,180,168,184,174,168,174,169,174}} *)
Now, we can do the same with our cache construction, and since we know that we only have 100 different points, we can restrict our cache size to a 100:
Map[makeCachedPF[Total[Boole@PrimeQ@Range[#]],<||>, 100],data]//Short//AbsoluteTiming
(* {0.166174,{169,183,172,180,183,180,179,172,181,176 <<9980>>,168,175,180,168,184,174,168,174,169,174}} *)
We see very significant savings in computation time, while the cache size was fully controlled and fairly small. And again, once the computation finished, the cache (internal variable used to store it) has been garbage-collected, so we don't have to think about that at all.
Obviously, in this case, because the number of different values was small, the initial memoized function would do just as well in terms of cache memory consumption. It turns out to be about twice faster (on this example), than the controlled cache version:
Map[makeMemoPF[Total[Boole@PrimeQ@Range[#]],<||>],data]//Short//AbsoluteTiming
(* {0.088639,{169,183,172,180,183,180,179,172,181,176 <<9980>>,168,175,180,168,184,174,168,174,169,174}} *)
However, in general, we may either not know how many different values the function would be computed on, or find it unacceptable to store memoized values for all those different points.
One thing I did not implement, which is possible to add, is a version where every time when a value already in cache is encountered again, it is moved in an cache association to the right. That would somewhat improve the cache, for the price of slowing down the cached value lookup from a cached function. It may make sense to do this, if the function being computed is relatively expensive. Adding such code is easy.
Conclusions
So, in conclusion, this is a very good question and there indeed may be an advantage in using such constructs in certain circumstances, in terms of automatic garbage collection of memoized definitions when they are no longer needed.
I've also shown how one can extend this technique to create cached versions of pure functions, which differ from memoized versions in that the size of the cache can be controlled, so that it does not exceed certain number of stored values.
Note that the presence of Association
in the language helps a great deal. One could probably do without it (e.g. using System`Utilities`HashTable
), but one would still need some hash table - like data structure that would be automatically garbage-collectable - which is what the usual approach based on DownValues
does not provide.