What does the construct f[x_] := f[x] = ... mean?
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?
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.
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.