Consider these two expressions:

expr1 = a d g[X, c]^2 + e g[X, f] + 3

expr2 = a d g[X, c]^2 + e X + 3

How do I check whether these expressions depend on X only as g[X, _]. More specifically, I want to check that any occurrence of X in a given expression must appear as the first argument of the two-variable function g, and no other way.

In the two examples above, expr1 satisfies this criteria, expr2 does not.

Right now I can think of only one way to check this:

myCheck[expr_] := FreeQ[expr /. g[X, _] :> OK, X];

Then, myCheck[expr1] yields True and myCheck[expr2] yields false. Are there any other ways -- ideally ones that traverse the expression only once? myCheck above traverses the expression twice.


3 Answers 3

expr1 = a d g[X, c]^2 + e g[X, f] + 3;
expr2 = a d g[X, c]^2 + e X + 3;

myCheck[expr_] := 
 Catch[ReplaceAll[expr, {g[X, _] -> OK, X :> Throw[False]}];
  True] (* Carl Woll's *)

testQ[expr_] := FreeQ[expr /. g[X, _] :> 1, X]

Comparing testQ with myCheck

n = 100000;

Do[testQ /@ {exp1, expr2}, n] // AbsoluteTiming

(* {0.635065, Null} *)

Do[myCheck /@ {exp1, expr2}, n] // AbsoluteTiming

(* {0.882478, Null} *)

The results might change for more complicated expressions.

  • $\begingroup$ I did the same benchmark on much more complicated expressions, and remarkably, the original one I proposed is faster than @CarlWoll 's . I wonder what's slowing down his method given that it goes through the expression once. Perhaps Throw and Catch are slow things? Any ideas? $\endgroup$
    – QuantumDot
    Commented Dec 8, 2018 at 20:44
  • $\begingroup$ @QuantumDot - I don't know; presumably overhead associated with Throw and Catch outweighs advantage of single pass. $\endgroup$
    – Bob Hanlon
    Commented Dec 8, 2018 at 21:00
  • $\begingroup$ Maybe checking twice whether every sub-expression matches some pattern is not much worse than checking once whether they match one of the two patterns? Anyhow, I have undeleted my proposal (which does not use Throw) so that you could check its performance (and verify whether Throw was guilty of lowering performance) on your complicated expressions. I would be grateful if you inform about results. $\endgroup$
    – MK.
    Commented Dec 8, 2018 at 22:49

If you only want to traverse the expression tree once, then you could do:

myCheck[expr_] := Catch[
    ReplaceAll[expr, {g[X,_]->OK, X:>Throw[False]}];

Your examples:





What about

myCheck[expr_] := Module[{iDontLikeYou=0},
expr/.{g[X,a_]-> whatever, X :>(iDontLikeYou++;X)};
iDontLikeYou === 0]

? Alternatively you could play with Abort[] or Return[False] (or something like that) instead of iDontLikeYou++ to stop evaluation immediately after first wrongly placed X is hit.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.