WolframLang: Function Memoization (Function that Cache Values)

By Xah Lee. Date: . Last updated: .

What is Function Memoization (Function that Cache Values)

Function Memoization is when a function remember its values, so when called, it can get the value from cache, instead of computing it.

This is useful when computing the function is expensive. typical example is when a function is recursively defined. e.g. factorial, fibonaci numbers.

Factorial Example

here's a way to define factorial recursively. 

(* factorial of 1 is always 1. we use Set (=) *)
factorial[1] = 1;

(* factorial of x depends on factorial x-1.
needs to be computed.
We use SetDelayed (:=). *)
factorial[x_] := factorial[x-1] * x;

(* test *)
factorial[10] === Factorial[ 10 ]
(* True *)
(* 3628800 *)

Factorial Function with Memoization

Here's example of factorial that remember computed values.

Clear[ factorial ];

factorial[1] = 1;
factorial[x_] := (factorial[x] = factorial[x-1] * x);

(* 
in
(factorial[x] = factorial[x-1] * x)
,
the computation of the right-hand-side factorial[x-1] * x
is set to the left-hand-side factorial[x], so
factorial[x] remembers the value, for a given x.
and when factorial[y] is called where y has been computed before,
it is returned right away.
*)

(* this makes the function remember its values computed before *)

(* check with builtin function *)
factorial[10] === Factorial[ 10 ]
(* True *)
(* 3628800 *)

Function Memoization Explained in Terms of Pattern Matching

the way this works is that assignment returns a value. a = b returs b. and, = has higher stickiness than := , so

f[x_] := f[x] = f[x-1] * x

is

f[x_] := (f[x] = f[x-1] * x)

here, we defined one single transformation rule. namely, f[x_]

Now, if user eval f[3], what happens?

The pattern f[x_] matches f[3], so it get replaced by (f[3] = f[3-1] * 3)

This is a new rule. The right-hand-side eval to (f[2] * 3) and the f[2] again matches f[x_] , to it becomes (f[2] = f[2-1] * 2).

f[2-1] becomes f[1] and it matches the f[1] = 1 so it is 1.

thus, we have

and we got these new rules.

Now, if we eval f[3] again, what happens?

in general, WolframLang will first try to match more specific pattern, then try more general pattern.

f[3] matches both f[3] = 6 and f[x_] := (f[x] = f[x-1] * x) , but the f[3] = 6 rule is more specific, so it applies first, and we got 6.

it's important to note, the FullForm of a = b is Set[a,b]. Which means, create a rule, so whever a occur, replace it by b.

and the FullForm of a := b is SetDelayed[a,b]. Which means, create a rule, so whever a occur, replace it by b, but eval b only at the time of replacement.

WolframLang: Define Function