# How to make a replacement, provided an inner rule applies

Consider:

expr /. (b[a_] * c_f /; !FreeQ[c, d[a]] :> (c /. (d[a] :> e) ))


Here's how it works: in expr, the products b[a]*c, with c being a large arbitrarily deep expression with head f, gets replaced with just c in which all the d[a]'s replaced with e. However, this replacement is supposed to happen only if the arbitrarily deep expression c has at least one d[a] in it.

But, I am afraid that the Condition of !FreeQ[c,d[a]] together with the second ReplaceAll is making the pattern matcher/searcher scan through c twice.

Is there a way to achieve this task by making the pattern matcher search through c only once?

Follow up question: would it be any harder to achieve this task if the inner rule had more structure?

expr /. (b[a_] * c_f /; !FreeQ[c, d[___, a, ___]] :> (c /. (d[left___, a, right___] :> e[left, {b}, right]) ))


In this case d is more complicated, and the replacement is more precise.

• Apart from the interesting intellectual problem, does the number of times the pattern engine traverses the expression actually impact performance or the result (perhaps because of side effects)? – MarcoB Mar 9 '16 at 17:01
• By "scan through f" I assume you actually meant "scan through c". Yes, it appears such a scan would recur. Why have the Condition in the first place though? – Daniel Lichtblau Mar 9 '16 at 18:54
• @DanielLichtblau Yes that's a typo. Without the condition, the expression b[a] f[(*stuff*)] would unintentionally get transformed to f[(*stuff*)] even if there is no d[a] inside f[(*stuff*)]. The b[a] pre-factor should disappear only if there is d[a] inside f[(*stuff*)]. – QuantumDot Mar 9 '16 at 21:39

While the concerns about performance degradation may in many cases be unwarranted, here is a way that would avoid double - traversal:

exp /. b[a_]*c_f :> With[{res = c /. d[a] :> e}, res /; res =!= c]


This uses the semantics of local variables shared between the body and the condition of the rule, and assumes that replacements change the original expression c. If the condition does not hold, the whole rule isn't considered matched, so is not applied.

• This is nice, but doesn't checking res=!=c require traversing through the whole expression again? – QuantumDot Mar 9 '16 at 17:13
• @QuantumDot It does, but this is done at even much lower level than what the pattern-matcher does, in the kernel. So for all intents and purposes, this does not count as another pattern-matching traversal, IMO. – Leonid Shifrin Mar 9 '16 at 17:14
• I came up with another way to do it (posted as an answer); can you see if it is a viable alternative that prevents double traversal? – QuantumDot Apr 28 '16 at 9:48

I came up with another way to do this:

expr /. b[a_]*c_f :>
Block[{$patternMatched}, With[{result = c /. (d[a] :> ($patternMatched = True; e))},
result /; $patternMatched]]  Once the outer pattern matches (b[a_]*c_f), a boolean is set up $patternMatched. Then, if the inner pattern matches (d[a] appears inside c) then \$patternMatched is set to True, so that the replacement is made. If the inner pattern fails to match, the Condition fails, stopping the outer replacement from happening.

• Looks like a valid alternative. Personally I try to avoid side effects, but this particular code looks fine to me. – Leonid Shifrin Apr 28 '16 at 13:37