What does the construct f[x_] := f[x] = ... mean?

Question

This question mentions "x := x = trickery".

What does defining a function as f[x_] := f[x] = ... do and what is it good for?

Answer 1

It is a simple way to implement Memoization. The trick is that if you define a function as

f[x_]:=f[x]=ExpensiveFunctionOf[x]

then when you for the first time call e.g. f[3], it will evaluate as

f[3]=ExpensiveFunctionOf[3]

which will evalulate the expensive function, and assign the result to f[3] (in addition to giving it back, of course). So if e.g. ExpensiveFunctionOf[3] evaluates to 7, it will assign f[3]=7.

The next time you call f[3], it will find that newly created definition of f[3] and use that in preference to the general rule. This means it will return the value 7 without calculating ExpensiveFunctionOf[3] a second time.

Answer 2

Memoization is perhaps the most common application, but it is not the meaning of that construct.

More generally it is a construct for a function that redefines itself. This has many uses beyond memoization. Consider this function:

f[y_] := (f[y] = Sequence[]; y)

It is used to remove duplicates in a list. When the function is first called with a particular argument (expression) it redefines itself, only for that argument, to Sequence[]. The next time it is applied to that expression it therefore resolves to Sequence[] (because the more specific definition has priority) and the expression is effectively removed. (Of course it must be reinitialized between lists unless you want to remove duplicates globally.)

f /@ {3, 5, 2, 3, 2, 4, 3}

{3, 5, 2, 4}

You can also write a function that changes its behavior after the first use.
Note the different pattern name to avoid conflict.

g[x_] := (g[y_] := y - 1; x + 1)

g /@ {1, 2, 3}

{2, 1, 2}

This can even be nested deeper:

g[x_] := (g[y_] := (g[z_] := z + 4; y - 1); x + 1)

g /@ {1, 2, 3}

{2, 1, 7}

---

Syntax for memoization

When using this construct for memoization it is often nice to use a named pattern for the entire left-hand-side, e.g.:

mem : f[x_] := mem = . . .

This is equivalent to f[x_] := f[x] = . . .. In this simple case it is not an improvement, but when the definition becomes longer it has the advantages of being:

• more concise
• less prone to error as there is less code to retype
• a convenient label for purpose of the construct

If one adopts this convention seeing mem : will immediately let one know this is a memoized function.

As a contrived example:

mem : combinations[set_Integer?Positive, choose_Integer?Positive] := 
  mem = set!/(choose! (set - choose)!)

Memoization is not the only application of a pattern that matches the entire left-hand-side and by using consistent pattern names for each application one can impart valuable metadata about the nature of the code to follow.

Reference:

• How does a construct like `i : func[arg_] := i = an expression using arg` work?

Answer 3

This is my first reply in this group. So please bear with me if I make any mistake, it would not be intentional, just lack of familiarity with the rules.

Although the replies above mention important aspects, I generally like to view things from alternative perspectives. I'd like to offer a few of those on this question. Understanding is enhanced by viewing the same thing from different angles.

The word "memoization" was already mentioned above by Leonid, you can also think of it as "caching". Consider it as an example of caching data to prevent re-computation. Using the Fibonacci numbers as a simple example, if you have a definition like

fib[n_]:=fib[n]=fib[n-1]+fib[n-2];
fib[0]=1;
fib[1]=1;
fib@5

??fib

then every time you evaluate fib@somethingalreadycomputed M will simply pull the result from memory and not compute it again. This type of construction ensures that you ONLY compute a new result if none is known already for the given argument. In fact, the very fact that the formula is shown at the bottom is exactly how M treats this internally: like a look-up table. You are guaranteed that the order in which ?? (Information) outputs the results is exactly how M looks these things up internally. So the formula is ONLY evaluated if no prior match is found. This is how a typical look-up table works in a software system, this has nothing to do with M. You go through your list sequentially, and at the first match, bail out with the result. That's why it's important to have a look-up table in the proper order, which M ensures us. ?? (Information) outputs exactly the way the look-up table is treated in the kernel.

Compare this with

Clear@fib;
fib[n_]:=fib[n-1]+fib[n-2];
fib[0]=1;
fib[1]=1;
fib@5

??

where the intermediate values are not defined, but have to be computed and re-computed every time you evaluate fib@someInteger. This can be atrociously inefficient for larger n when the function has above-linear complexity.

Another perspective is to liken this to (a particular implementation of) the proxy pattern in object-oriented design. For example, in Java or C# code you frequently find constructs such as

public void displayImage() {
       if (image == null) {
           image = new RealImage(filename);
        } 
        image.displayImage();
    }

If the image doesn't exist, create it, then display it. If it does exist, skip the creation part, and display immediately what we have already in memory. The visitor pattern in OO design also oftentimes works like this. You check for existence, and you base your next decision on the answer to the existence question. This is the most efficient way to ensure that every unique object is only computed once ever.

Another perspective to think of this is as a combination of computation and data. When you compute something with a formula, you are performing a computation. But when you look up something from memory, you are not computing, you are pulling data and return data. This construction is a very convenient way to combine computation and data and let the system decide which one is to be done at execution time. That's actually a very important concept in software design: data vs. computation. We may not think about it this way because it's so easy in M.

Next,

TreeForm@Hold[fib[n_]:=fib[n]=fib[n-1]+fib[n-2]]

tells us that the SetDelayed is evaluated as the outermost function. Thus, the parentheses are

fib[n_]:=(fib[n]=fib[n-1]+fib[n-2]);

Now it's easy to see what happens. Every time you call fib[someInteger], we get the result of an equation (Set). In M the result of an equation (Set) is either the known result (if the evaluated left-hand side is known), or the result of the computation of the right-hand side (if the left-hand side is not known -- yet!). In the latter case it now assigns it to the evaluated left-hand side fib[n] and will stored as such, as downvalues are attached to the left-hand side of their assignments.

Answer 4

It's ... oh, why not let the docs speak:

tutorial/FunctionsThatRememberValuesTheyHaveFound

(in Doc center)

Edit

You may also find additional information by searching for "memoization" on this site. This has always been a great trick to avoid having to re-evaluate the result of a computationally intensive function call. In the above link, it is also used to do recursion.

I'll try to explain things without the added complication of recursion: The basic idea is that when you define a function using

f[x_]:= x^2

you are using x as the name of a pattern playing the role of a dummy variable. The := (meaning SetDelayed) has the property of leaving whatever is on the right-hand side unevaluated until it's needed, and this happens when a pattern matching the left side is encountered, say, f[4].

To make Mathematica remember things, you can't assign a value to a pattern, so you would normally say

f[4]=16

Now such definitions are found by Mathematica before it looks for matching pattern definitions such as f[x_]:=x^2 above. So in other words, if I type f[4] after having executed the above two lines, my "function definition" doesn't actually have to be used at all because the system already knows the result for the specific value 4.

The memoization trick now combines the above lines, which would lead to

f[x_]:=f[x]=x^2

The right-hand side of SetDelayed is now telling us to take whatever was passed in through the dummy variable x and assign this to f[x] using Set (the = sign). The result of that last operation is that a "non-pattern" f[x] with a specific new value of x has been defined for later use, and the value that got assigned to that is also returned as the replacement for the pattern f[x_] (i.e., the function value in the initial function call).

Whenever a new x is passed to f[x], we now get a new "permanent" definition added to the memory so that the function (the pattern) doesn't need to be evaluated again for that x.

It's best to play around with this yourself by defining a function along the lines above, and then periodically checking what Mathematica knows about your function by typing ?f.

Answer 5

It also has another practical side. If you have a random function, which

• you only want to evaluate once, but
• you don't know where exactly it will be evaluated or
• you want to declare it before the parameters it depends on are defined, and
• you want it to be the same after the first evaluation, for any subsequent call,

you can use the memoization trick:

initPopulation := initPopulation = InitializeRandomPopulation[args..];

(* lots of computation *)
(* the above *args* (on which the function depends!) are defined only now *)
(* and finally we got to the part where we compute the initial population *)

pop1 = initPopulation

(* use the very same initial population again and again... *)

pop2 = initPopulation 

...