# Function that caches when it returns unevaluated

How would you go about implementing a function that caches not the result but the fact that it didn't match a pattern? So that it doesn't waste time recomputing a complex time-consuming pattern condition every time it needs to evaluate the expression.

f[i_] := Module[{res},
res /; (
res = i^2(* some time consuming calculation *);
Print[i];
res < 8)]


I'd like that if I run the following example I don't get two Print statements but only one.

f[20];f[20];


An ideal solution would provide a way to make the pattern matcher skip a particular definition if it previously found it didn't fit. However, I'm happy enough with a nice way to make MMA just "let the unevaluated expression be" without wasting time every time it reevaluates it only to find it returns unevaluated.

So far I'm thinking of

Module[{fMatch},
fMatch[_] := True;
f[i_] := Module[{res},
res /; fMatch[i] && (
res = i^2
(* some time consuming calculation *);
Print[i];
fMatch[i] = res < 8)]
]


which seems to work I guess. You have better ideas, or think that needing this kind of construction is a sign of bad programming?

-
If you cache failures, is there any reason to not cache previously computed values as well? –  Leonid Shifrin Jan 24 '12 at 10:23
@Leonid and Rojo I believe there is some built-in caching on conditions already. See the doc page for Update. I'd love to dig into this, but I need to run now. Perhaps you already know how it works? –  Szabolcs Jan 24 '12 at 11:30
@Szabolcs Yes, I used Update in my work a few times when it was absolutely necessary, and I even answered some question about it on MathGroup, in one of the threads:groups.google.com/group/comp.soft-sys.math.mathematica/…. I believe however that the case at hand is somewhat different, at least as considered up to now. –  Leonid Shifrin Jan 24 '12 at 11:41
@Szabolcs Wow, I had never come into Update docs before and I hope I'm not bitten by a bug of the sort any time; I wouldn't know when to use it but after it bit me hard. Reading MathGroup threads now –  Rojo Jan 24 '12 at 12:39
@Leonid no reason not to cache results, just said it to stress what I was not trying to do, not what I was trying not to do –  Rojo Jan 24 '12 at 12:42

The following definition of f uses an auxiliary symbol to cache all results, whether they meet the required condition or not:

longCalculation[x_] := (Print["calculating value for ", x]; x)

Module[{cache}
, m:cache[x_] := m = longCalculation[x]
; f[x_] := Module[{r = cache[x]}, r /; r < 8]
]


Here is a sample use:

In[61]:= f /@ Mod[2Range[20], 10]
During evaluation of In[61]:= calculating value for 2
During evaluation of In[61]:= calculating value for 4
During evaluation of In[61]:= calculating value for 6
During evaluation of In[61]:= calculating value for 8
During evaluation of In[61]:= calculating value for 0
Out[61]= {2,4,6,f[8],0,2,4,6,f[8],0,2,4,6,f[8],0,2,4,6,f[8],0}

-
WReach, I notice that you have the Fanatic badge, yet you don't post all that often. I hope you'll post more; in the past you have provided some of the most enlightening answers of all. –  Mr.Wizard Apr 30 '12 at 3:47
@Mr.Wizard Thanks for the encouragement. Even though I scan the site daily, I can usually only post once a week or so. By the time that rolls around, I find I have nothing to add to existing responses -- this site has a thriving and knowledgeable community. Also, there is a good chance that everything I know is already posted here or on the old site :) –  WReach Apr 30 '12 at 18:33

This solution makes use of an undocumented symbol that, if returned by an iteration, makes the evaluator stop searching and return the function unevaluated (as far as my tests show): SystemPrivate$Localized Say we have some slow condition that will match if the argument is greater than 8 longCheck[i_] := i > (Pause[2]; 8)  Now we do ClearAll[f]; i : f[j_?longCheck] := i = 3 j i : f[_] /; (i = SystemPrivate$Localized) := i

f[2] // AbsoluteTiming
f[9] // AbsoluteTiming
f[2] // AbsoluteTiming
f[9] // AbsoluteTiming


to get

{2.0011145, f[2]}

{2.0001144, 27}

{0., f[2]}

{0., 27}

-

If you allow for the use of Defer you could use a form similar to this:

ClearAll[f]

f[i_] :=
Module[{res},
Print["body"];
f[i] = Defer[f[i]];
res = i^2;
(f[i] = res) /; (Print["condition"]; res < 8)
]


I broke up your Condition test to be more like what I believe the actual use of /; inside RHS Module is likely to be. I give one Print for the body operation(s) and another for the condition.

This starts by assuming that the condition is going to fail and setting f[i] = Defer[f[i]]. Then, iif the condition passes, f[i] is again redefined to the return value. If for some reason you do not want to cache the condition-pass value you could use Unset here: (f[i] =.; res) /;.

This is essentially equivalent to this:

ClearAll[f]

f[i_] :=
Module[{res},
Print["body"];
res = i^2;
res /; (Print["condition"]; res < 8)
]

a : f[i_] := a = Defer[a]

-

The cleanest thing I've found is similar in spirit to what you are already doing. I set up a function validQ which checks whether a particular expression has been tested yet. If it has, then it returns valid otherwise it checks whether it is valid according to your test.

I find the input validation using PatternTest preferable.

validQ[expr_] := With[{vQ = getValid[expr]}, If[Head[vQ] === getValid, True, vQ]]

f[i_?validQ] :=
Module[{res}, res /; (res = i^2(*some time consuming calculation*);
Print[i];
getValid[i] = res < 8)]


Here is the result using 20 which should print only once and 1 which should print twice.

In[3]:= f[20]; f[20];

20

In[4]:= f[1];f[1];

1

1


EDIT: Note that this will slow down quite a lot if you are going to be testing a huge number of values since downvalues are created for each case.

-