This question mentions "
x := x = trickery".
What does defining a function as
f[x_] := f[x] = ... do and what is it good for?
It is a simple way to implement Memoization. The trick is that if you define a function as
then when you for the first time call e.g.
which will evalulate the expensive function, and assign the result to
The next time you call
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:
This function is used to remove duplicates in a list. It works because after the first time the function is called for a particular argument, for that argument the function is redefined to
You can also write a function that changes its behavior after the first use.
This can even be nested deeper:
A note regarding syntax
When using this construct for memoization it is often nice to use a named pattern for the entire left-hand-side, because it is:
All these things are most useful when the definition is rather long.
After getting used to this convention seeing
|show 3 more comments|
It's ... oh, why not let the docs speak:
(in Doc center)
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
you are using
To make Mathematica remember things, you can't assign a value to a pattern, so you would normally say
Now such definitions are found by Mathematica before it looks for matching pattern definitions such as
The memoization trick now combines the above lines, which would lead to
The right-hand side of
Whenever a new
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
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
then every time you evaluate
Compare this with
where the intermediate values are not defined, but have to be computed and re-computed every time you evaluate
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
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.
tells us that the
Now it's easy to see what happens. Every time you call
It also has another practical side. If you have a random function, which
you can use the memoization trick: