2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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)? $\endgroup$
    – MarcoB
    Commented Mar 9, 2016 at 17:01
  • $\begingroup$ 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? $\endgroup$
    – Daniel Lichtblau
    Commented Mar 9, 2016 at 18:54
  • $\begingroup$ @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*)]. $\endgroup$
    – QuantumDot
    Commented Mar 9, 2016 at 21:39

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is nice, but doesn't checking res=!=c require traversing through the whole expression again? $\endgroup$
    – QuantumDot
    Commented Mar 9, 2016 at 17:13
  • 1
    $\begingroup$ @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. $\endgroup$
    – Leonid Shifrin
    Commented Mar 9, 2016 at 17:14
  • $\begingroup$ 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? $\endgroup$
    – QuantumDot
    Commented Apr 28, 2016 at 9:48
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Looks like a valid alternative. Personally I try to avoid side effects, but this particular code looks fine to me. $\endgroup$
    – Leonid Shifrin
    Commented Apr 28, 2016 at 13:37

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.