# How to do memoization together with evaluation of a complicated function

UPDATE 2: much shorter version

Given a list of paired indices {i, j}={{1,2}, {3,4}, …}, I need to first evaluate a rather complicated function test[i,j,x] (because it's too computationally costing) and then assign each copy to a function named after {i, j} with memoization. Specifically, I need an expression (as elegant as possible, though timing is more important) which effectively does the following things:

f12[x_]:=f12[x]=Evaluate[test[1,2,x]]
f34[x_]:=f34[x]=Evaluate[test[3,4,x]]
…


Note that in this example Evaluate has no effect (due to memoization), but I want it to be done first!

UPDATE 1

Thank @SimonWoods for proposing a Function approach and @m_goldberg for proposing a replacement rule approach. However both approaches are not quite satisfying in their own ways. For the Function approach, I confirmed that in the simplest MWE (with no indices in f) it does assign x^2 instead of test[x] to f[x]:

(f[x_] := f[x] = #) &[test[x]]
?f


But when I want to create {f12, f34, …} I have no idea how to generalize this approach because the existence of the extra # ruins the function definition

(ToExpression["f" <> ToString[#1] <> ToString[#2]][x_] := ToExpression["f" <> ToString[#1] <> ToString[#2]][x] = #) &[test[x]] @@@ {{1, 2}, {3, 4}}
?f12


The replacement rule approach does address this issue as shown in @m_goldberg's answer. However as I said the function test also depends on {{1,2}, {3,4}, …}. Specifically, one can think of this complicated function as either

test[i_, j_, x_]:=Module[{some stuff}, some complicated operations which use {i, j} and return an expression in x]


or

test12[x_]:=Module[{some stuff}, some complicated operations which return an expression in x]
test34[x_]:=Module[{some stuff}, some complicated operations which return another expression in x]


and so on. In other words, I would like to assign the evaluated result of test12[x] (or test[1,2,x]) to f12[x], that of test34[x] (or test[3,4,x]) to f34[x], so on so forth. (I should have made this point more transparent. Apology.) But the replacement rule approach seems to fail at this requirement: the code

((ToExpression["f" <> ToString[#1] <> ToString[#2]][x_] :=
ToExpression["f" <> ToString[#1] <> ToString[#2]][x] =
expr;) /. expr -> test[#1, #2, x] &) @@@ {{1, 2}, {3, 4}}


does not give f12[x_]:=ToExpression[f<>ToString<>ToString][x]=test[1,2,x]; it gives expr instead. So both approaches still do not meet my need yet.

My goal is to create a bunch of functions {f12, f34, …} on the fly for later calculation. Those functions involve a pre-defined Module (let me call it test) which gives a rather complicated expression. For simplicity let us first consider the following example:

(ToExpression["f" <> ToString[#1] <> ToString[#2]][x_] :=
ToExpression["f" <> ToString[#1] <> ToString[#2]][x] = x^2;) & @@@ {{1, 2}, {3, 4}}


This example defines functions f12[x] and f34[x] to be x^2 with memoization which can be easily seen by using Downvalues:

f12[#] & /@ Range; DownValues[f12]

{HoldPattern[f12] :> 1, HoldPattern[f12] :> 4, HoldPattern[f12[x_]] :>
(ToExpression["f" <> ToString <> ToString][x] = x^2)}


The last element of DownValues[f12] is of crucial importance as it tells us the expression of f12[x] is x^2.

Now let me use a different approach. I define a function using Module

test[x_] := Module[{a}, a = x; FullSimplify[Log[Exp[a^2]], Assumptions -> a > 0]]


which essentially gives me x^2 upon evaluation. Follow the same strategy let us define f12 and f34:

(ToExpression["f" <> ToString[#1] <> ToString[#2]][x_] :=
ToExpression["f" <> ToString[#1] <> ToString[#2]][x] = test[x];) & @@@ {{1, 2}, {3, 4}}


and look at again the Downvalues of f12:

f12[#] & /@ Range; DownValues[f12]

{HoldPattern[f12] :> 1, HoldPattern[f12] :> 4, HoldPattern[f12[x_]] :>
(ToExpression["f" <> ToString <> ToString][x] = test[x])}


Note that now the last element of DownValues[f12] involves the function test. However this is not what I want! The reason is that as I mentioned above in my calculation test[x] is a rather complicated expression (which depends on the indices {{1,2}, {3,4}, …}) simplified within the Module, and I would like to assign the simplified expressions to {f12, f34, …} instead of computing them in situ. I tried

(ToExpression["f" <> ToString[#1] <> ToString[#2]][x_] :=
ToExpression["f" <> ToString[#1] <> ToString[#2]][x] =
Evaluate[test[x]];) & @@@ {{1, 2}, {3, 4}}


But DownValues[f12] simply gives me

{HoldPattern[f12] :> 1, HoldPattern[f12] :> 4, HoldPattern[f12[x_]] :>
(ToExpression["f" <> ToString <> ToString][x] = Evaluate[test[x]])}


which is not useful.

In short, I would like to see any manipulation with test[x] that gives me the DownValues to be HoldPattern[f12[x_]] :> (ToExpression["f" <> ToString <> ToString][x] = x^2. In other words, I need test[x] to be evaluated first and then assigned to {f12, f34, …} with memoization. On this site I think (two of) the best articles talking about memoization are this one and this one, but I think neither solves my problem…

• How about With[{t = test[x]}, f[x_] := f[x] = t] – Simon Woods May 19 '14 at 20:05
• @SimonWoods, it's not working: try f[#] & /@ Range you'll get {x^2, x^2, x^2, x^2, x^2} instead of {1, 4, 9, 16, 25}. – Leo Fang May 19 '14 at 20:30
• Oops, sorry, missed that. Maybe Function instead: (f[x_] := f[x] = #) &[test[x]] – Simon Woods May 19 '14 at 21:30
• @SimonWoods, this simple example works but it fails in a more complicated situation. Please see my updated text. Thank you. – Leo Fang May 20 '14 at 3:24

EDIT

ClearAll[test,"f*"];
test[i_,j_]:=
Block[{x},
Print@"test";
FullSimplify[Log[Exp[x^2]],Assumptions->x>0]i+j];
indices=Partition[Range,2];
syms={Symbol["f"<>StringJoin[ToString/@#]],test[Sequence@@#]}&/@indices;
(#1[x_]:=#1[x]=#2)&@@@syms;


test

test

test

test

test

f34


79

DownValues[f34]


{HoldPattern[f34] :> 79, HoldPattern[f34[x_]] :> (f34[x] = 4 + 3 x^2)}

• Thank you @mfvonh for your answer. Sorry for late reply -- I am on a trip and have no enough time to work things out. However I think similar answers have been provided and the main issue, as I pointed out in the updated text, is that you assign "unevaluated" test functions to f, which is not what I want. – Leo Fang May 24 '14 at 16:34
• @LeoFang Oh I see. I didn't understand that part of the issue was scoping x. I've taken another shot. – mfvonh May 24 '14 at 17:06
• Thanks @mfvonh for the update! It seems to me that your answer fits all my requirements! In particular the one-line definition (#1[x_]:=#1[x]=#2)&@@@syms; is amazing -- is it because you collect the function names and expressions before assigning them? By the way, if you remove the line a=x; and change the one-line definition (#1[x_]:=#1[x]=#2)&@@@syms; to (#1[a_]:=#1[a]=#2)&@@@syms;, the whole trick is still working without using a global variable x (don't know why though). – Leo Fang May 28 '14 at 2:47
• Aha, a in Block is a global variable, and that's why the change I found is working. – Leo Fang May 28 '14 at 3:03
• Also, be careful with the naming of the f. If you have indices {11,5} and {1,15}, for example, you will run into problems. – evanb May 28 '14 at 17:58

Will this approach work for you? If it will, then this is an answer :)

test[x_] :=
Module[{a}, a = x; FullSimplify[Log[Exp[a^2]], Assumptions -> a > 0]]
Clear @ "f*"
(((ToExpression["f" <> ToString[#1] <> ToString[#2]][x_] :=
ToExpression["f" <> ToString[#1] <> ToString[#2]][x] = expr;) &) /.
expr -> test[x]) @@@ {{1, 2}, {3, 4}};
f12 /@ Range @ 4;
DownValues @ f12

{HoldPattern[f12] :> 1,
HoldPattern[f12] :> 4,
HoldPattern[f12] :> 9,
HoldPattern[f12] :> 16,
HoldPattern[f12[x_]] :>
(ToExpression["f" <> ToString <> ToString][x] = x^2)}

• this example works but it fails when I need test to take the values {{1,2}, {3,4}, …}. Please see my updated text. Thank you. – Leo Fang May 20 '14 at 3:25

I think the trick is to use a Function approach and memoize test itself, as follows. I'll use a slightly more complicated test function, and it will print EXPENSIVE! when the hard work is done:

 test[i_,j_] := test[i,j] = Function[x, Evaluate[Print["EXPENSIVE!"]; x^(i^j)]]
f[i_,j_][x_]:= f[i,j][x] = test[i,j][x]

f[1,2][x]
(* EXPENSIVE! *)
(*   x    *)
f[1,2]
(*   7    *)

?f
(*
f[1,2]=7
f[1,2][x]=x
f[i_,j_][x_]:=f[i,j][x]=test[i,j][x]
*)
?test
(*
test[1,2]=Function[x$,x$]
test[i_,j_]:=test[i,j]=(Print[Expensive!];Function[x,Evaluate[x^i^j]])
*)
f[3,2]
(* EXPENSIVE! *)
(* 262144 *)
f[3,2]
(* 19683 *)
?f
(*
f[1,2][x]=x
f[3,2]=19683
f[3,2]=262144
f[i_,j_][x_]:=f[i,j][x]=test[i,j][x]
*)
?test
(*
test[1,2]=Function[x$,x$]
test[3,2]=Function[x$,x$^9]
test[i_,j_]:=test[i,j]=(Print[Expensive!];Function[x,Evaluate[x^i^j]])
*)


Note also since f is curried (that is, the parameters are broken up into more than one set of [brackets]) you can do things like

allfuncs = f@@@ {{1,2}, {3,2}, {5,-1}}
(* {f[1,2], f[3,2], f[5,-1] *)
Through[allfuncs]
(* EXPENSIVE! *)  (* just one, because test[1,2] and test[3,2] exist already... *)
(* { 2, 512, 2^(1/5) } *)


Also note that you can pass around the expressions f[1,2] before doing the corresponding hard work, since test only gets evaluated when f[1,2] is applied to some quantity. This makes f somewhat lazy... only doing the hard work the first time, when it is needed.

Also note that one need not memoize f itself, if all of the expensive work is really being done inside test.

• Dear @evanb, thanks for sharing this approach. The key issue in my question (and your answer) is that I need test to run and generate a complicated expression for subsequent calculation before it's memorized. Here you assumed that in test there are known expressions Print["EXPENSIVE!"] and x^(i^j), which is not my case. For example, as you said the hard work is done only when f[1,2] is applied, but then every time I need f[1,2] for different x I have to generate the expression from test and substitute the value of x, which does not save time (it's not even memoization!). – Leo Fang May 21 '14 at 18:35
• Look at the first ?test. It has test[1,2]=Function[x$,x$], meaning that the i=1 and j=2 dependence has been taken care of. If you want f[1,2] and f[1,2] and f[1,2][foo], test is only evaluated one time. I thought that this is what you wanted? – evanb May 21 '14 at 18:40
• Well, the way I came upon this approach was to think about the different kinds of objects you wanted in your computation. You wanted intermediate (expensive to compute) functions, and then the results of applying said functions to some quantities. It seemed natural to break up the evaluation that way too. There might be a one-step method to getting what you're looking for, but I bet it must be tricky... – evanb May 21 '14 at 18:48
• Sure! I am curious---what is the constraint / problem? f[1,2] should behave just like the symbol f12 you originally wanted---that test exists at all should be totally invisible to the rest of your code. You may find (if you memoize too many things) that your calculation slows dramatically. This can be a result of memory constraints. If that happens you might check out mathematica.stackexchange.com/questions/19536/… or simply not memoize f. – evanb May 23 '14 at 17:44
• @mfvonh's solution and mine are along the same lines. In his case, the evaluation of test is done when evaluating syms (and not (#1[x_]:=#1[x]=#2)&@@@syms;), so that we both used the "evaluate-the-i/j-dependence-first, store that answer, use that answer in another definition" method. – evanb May 28 '14 at 18:02

I have included my own test function. It takes quite long to calculate and it has an unspecified variable x.

k = 4;
j = 7;
Clear@x
test[k_, j_] :=
Simplify[Integrate[E^(k y^3 + j ) y^x Log[y], {y, k, j}]]

Clear@f
f[i_, j_, z_] :=
(Block[{x},
ReleaseHold@Hold[SetDelayed][Hold@f[i, j, x_], test[i, j]]];
f[i, j, z])


Now, we have

Timing[f[1, 2, 3] // N]

{6.654387,9067.81 -5.60026*10^-12 I}


This took quite long, because test[1,2] had to be calculated. But if we use the same i and j now, things are faster

Timing[f[1, 2, 4] // N]

{0.005643,17423.1 -1.12005*10^-12 I}


The idea is similar to that in usual memoization. f[1,2,x_] is a more specific pattern than f[i_,j_,z_], so the newer definition will be prioritised. This technique using ReleaseHold and wrapping a head in Hold seems to be something only I use. To get an basic idea of what is going on, imagine Hold and ReleaseHold are not there, they only change the order of evaluation.

A more detailed explanation is as follows. I try to avoid having SetDelayed as a head of an expression on the RHS of another SetDelayed, or inside Block. Unexpected things can happen if we nest scoping constructs like this. So alternatively we could have written the following, in which the order of evaluation is the same.

Clear@g
g[i_, j_, z_] :=
(Block[{x}, g[i, j, x_] := Evaluate@test[i, j]];
g[i, j, z])


But then after evaluating g[1,2,3], we have a definition like this

g[1, 2, x$_] := ...  Where we have x$ instead of x, which makes the code fail.

• Thank you @Jacob Akkerboom for your answer. Sorry for late reply -- I am on a trip and have no enough time to work things out. Your answer looks interesting and seems to be working. I'll think about it when my trip is over. – Leo Fang May 24 '14 at 16:36
• @LeoFang ok, no worries, enjoy your trip :). By the way I also like the answer by evanb, just an alternative here. – Jacob Akkerboom May 24 '14 at 22:53
• Thanks. I like evanb's answer too. The ReleaseHold/Hold business is always a mystery to me :P – Leo Fang May 28 '14 at 3:10