24
$\begingroup$

Given a symbol t and an expression expr, how can I determine whether or not the symbol t appears somewhere in expr?

The best solution I have up with so far is:

Block[{t,s},(expr/.t->s)=!=expr]

which will return True if t is in expr, and False otherwise.

But this feels a bit like a hack because it's not really using /. because it's the right tool, but rather because /. happens to need to search through expr in order to do its unrelated task. This results in having to search through expr at least three times (I think?): once for the /., and twice for each side of the =!=, when clearly its possible to find t in only one search.

Improve this question
$\endgroup$
5
  • 10
    $\begingroup$ -1? Sure the answer is obvious once you know it, but I spent a very long time looking for an answer, and even longer trying to code my own answer. It's not like FreeQ is a terrible descriptive function name, and it's not listed in the 'Patterns' Guide, or the 'Testing Expressions' guide, or a bunch of other guides that might seem relevant to a newish user. $\endgroup$
    – Ian Hincks
    Commented Aug 23, 2012 at 17:42
  • 3
    $\begingroup$ It's in "Testing and Searching List Elements" at least, but I have to agree that the omission of FreeQ[] in the "Testing Expressions" is a most unfortunate omission. $\endgroup$
    – J. M.'s missing motivation ♦
    Commented Aug 23, 2012 at 17:49
  • 1
    $\begingroup$ @J.M. i filed FreeQ as a suggestion to be added to "Testing Expressions" $\endgroup$
    – user21
    Commented Aug 23, 2012 at 17:51
  • 2
    $\begingroup$ Also even if it is obvious and easy to find, at least the question makes sense, is well-written, and doesn't need mind-reading skills to answer. This is more than can be said for lots of others that people upvote $\endgroup$
    – acl
    Commented Aug 23, 2012 at 18:44
  • 5
    $\begingroup$ Don't forget FreeQ takes a levelspec optional argument. Can be useful if your quarry is hiding deep inside. Also there is Internal`DependsOnQ[expr,var] which attempts (operative word, that) to determine if expr has a functional dependence on x. Can be useful for tasks where detecting literal symbol presence is not quite what is wanted. Example: In[1]:= Internal`DependsOnQ[f[x], x] Out[1]= True $\endgroup$
    – Daniel Lichtblau
    Commented Aug 23, 2012 at 19:08

2 Answers 2

Reset to default
23
$\begingroup$

Try FreeQ

FreeQ[x^2, t]
(*True*)
FreeQ[x^2, x]
(*False*)
Improve this answer
$\endgroup$
0
11
$\begingroup$

ruebenko provides the built-in function, but supposing FreeQ was not provided we can find another way. You are on the right track to use ReplaceAll, but it would be much better to give a result as soon as the search pattern is found.

freeQ[expr_, pat_] :=
 Catch[expr /. pat :> RuleCondition@Throw[False, "freeQ"]; True, "freeQ"]

RuleCondition (1)(2)(3) is needed in the case that expr is Hold[ ] or the Throw will never evaluate.

Creating a massive expression (~1GB) and doing Timings (each in a separate session to circumvent caching) shows that this is reasonably fast.

big = Expand[(1 + x + y)^200 (2 - q)^150];

! FreeQ[big, q] // Timing

{1.03, True}

! freeQ[big, q] // Timing

{1.311, True}

Block[{q, s}, (big /. q -> s) =!= big] // Timing

{6.739, True}

Another approach that is cleaner, but perhaps less didactic, that will also return as soon as the pattern is found uses Cases:

freeQ2[expr_, pat_] :=
   {} === Cases[expr, pat, {0, -1}, 1, Heads -> True]

! freeQ2[big, q] // Timing

{0.983, True}

An important difference is that ReplaceAll (short form /.) will scan from the outside in while Cases, like most Mathematica functions, will scan inside out. See:

And more examples:

Improve this answer
$\endgroup$
6
  • $\begingroup$ @Mr.Wizard If I am interested in testing for more than one variable I defined freeQ[a_, b_] := FreeQ[a, b] /; Length[b] <= 1; freeQ[a_, b_] := And @@ Map[FreeQ[a, #] &, b] /; Length[b] > 1 Is this the most efficient way to proceed? Why isn't it the default behaviour? $\endgroup$
    – chris
    Commented Aug 23, 2012 at 18:57
  • $\begingroup$ @chris I'd suggest trying Alternatives: FreeQ[expr, x | y | z] Or do you mean something else? $\endgroup$
    – Mr.Wizard
    Commented Aug 23, 2012 at 19:00
  • $\begingroup$ I understand your answer as I should use freeQ[a_, b_List] := FreeQ[a, Or@@b]/; Length[b] > 1 . (I was after FreeQ taking lists) $\endgroup$
    – chris
    Commented Aug 23, 2012 at 19:07
  • $\begingroup$ @chris no, I mean: freeQ[a_, b_List] := FreeQ[a, Alternatives @@ b] -- see Alternatives. $\endgroup$
    – Mr.Wizard
    Commented Aug 23, 2012 at 19:09
  • $\begingroup$ Thanks. I guess I have to wrap my head around Trott-Strzebonski, now. :) $\endgroup$
    – rcollyer
    Commented Aug 23, 2012 at 19:20

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.