7
$\begingroup$

Why would this work to replace the head b with newHead:

b[c, d] /. head_[arg__] :> newHead[arg]
(* newHead[c, d] *)

but when b is nested within another head a, only a is replaced using the same rule:

a[b[c, d]] /. head_[arg__] :> newHead[arg]
(* newHead[b[c,d]] *)

Using ReplaceRepeated (//.), and HoldPattern did not help:

a[b[c, d]] //. head_[arg__] :> newHead[arg]
a[b[c, d]] /. HoldPattern[head_[arg__]] :> newHead[arg]
a[b[c, d]] //. HoldPattern[head_[arg__]] :> newHead[arg]
(* newHead[b[c, d]] *)

My question is: Is there any way to replace both a and b with newHead using a transformation rule?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
16
$\begingroup$

Use Replace instead of ReplaceAll

Replace[a[b[c, d]], head_[arg__] :> newHead[arg], {0, Infinity}]

newHead[newHead[c, d]]

ReplaceAll fails to do what you want because it acts from the outside in. Once it found a match (the entire expression) on the outside, its job was done. Replace on the other hand, acts from inside out.

Improve this answer
$\endgroup$
14
  • $\begingroup$ Thank you! Do you know why Replace work but not ReplaceAll? $\endgroup$
    – seismatica
    Jul 28, 2014 at 2:34
  • 1
    $\begingroup$ @seismatica see my update. $\endgroup$
    – RunnyKine
    Jul 28, 2014 at 2:44
  • $\begingroup$ Am I correct in saying that the reason //. would still not work is that each time the rule is repeated, it keeps on replacing the newHead again with newHead, without ever touching the b? $\endgroup$
    – seismatica
    Jul 28, 2014 at 3:04
  • 2
    $\begingroup$ @seismatica It should touch the inside heads in that case. You could do that with (head: Except[newHead])[arg__] to avoid infinite recursion. $\endgroup$
    – mfvonh
    Jul 28, 2014 at 3:08
  • 2
    $\begingroup$ @seismatica Compare a[b[c[d]]] /. x_ /; Print[x] -> x and Replace[a[b[c[d]]], x_ /; Print[x] -> x, {0, Infinity}]. Notice the order, and how the second doesn't test heads like a and b alone. This is because Replace tries to transform the "entire expression", and with the levelspec we have told it to do this at each level. So it starts at the inner parts of the expr and keeps widening its selection as it looks for a match. ReplaceAll is only replacing parts, so it can just walk forward through the tree. It "quits" because it replaces the whole expr and doesn't test the new part $\endgroup$
    – mfvonh
    Jul 28, 2014 at 12:16
11
$\begingroup$

This question has essentially been asked many times before, perhaps most recently here:

I addressed it myself when I demonstrated the use of Replace and FixedPoint in place of ReplaceRepeated to get the standard traversal in:

As already explained by RunnyKine ReplaceAll and ReplaceRepeated traverse the expression in an unusual way within the context of Mathematica. See my self-Q&A for some examples:

Further, as stated in the documentation:

ReplaceAll looks at each part of expr, tries all the rules on it, and then goes on to the next part of expr. The first rule that applies to a particular part is used; no further rules are tried on that part, or on any of its subparts.

Combined with the traversal order this means that inner expressions will never be replaced if they are part of a larger expression that matches a rule.

mfvonh comments that you could use:

a[b[c, d]] //. (head : Except[newHead])[arg__] :> newHead[arg]

newHead[newHead[c, d]]

However this is inefficient as the entire expression is rescanned for each replacement. I explored this issue in some detail here:

seismatica wrote:

I think I now know (how) ReplaceAll scans an expression. I'm still confused about how it replaces its matches. For example h[h[u, h], h] /. x : head_[arg__] /; Print[x] :> x finds all heads h, yet h[h[u, h], h] /. h[arg__] :> k[arg] only replaces the outermost h. @mfvonh mentions in his comment that "ReplaceAll "quits" because it replaces the whole expr and doesn't test the new part". If that's the case, then why would h[h[u, h], h] /. h :> k even though when any h is replaced, the expressions would also change.

Each case you cite is different from the original. In the first example you use a Condition that never is True, therefore every part of the expression that matches the pattern (without the condition) is checked (and printed) as ReplaceAll searches in vain for a match. Note how the behavior changes if we use a condition that is always True:

h[h[u, h], h] /. x : head_[arg__] /; (Print[x]; True) :> x

h[h[u,h],h]

h[h[u, h], h]

The second example highlights an important yet perhaps subtle difference: only entire expressions that are replaced are skipped for further matching and replacement. An expression head is like any other part of an expression and it can be replaced independently, therefore you can use /. to replace all heads of a certain kind (or which match a certain pattern) but you must not include arguments along with them.

Consider these examples:

SeedRandom[0]
expr = RandomInteger[9, {3, 2, 3}]

{{{7, 0, 8}, {2, 1, 5}}, {{8, 0, 6}, {7, 2, 1}}, {{0, 6, 1}, {2, 8, 6}}}

expr /. {x__} :> h[x]

h[{{7, 0, 8}, {2, 1, 5}}, {{8, 0, 6}, {7, 2, 1}}, {{0, 6, 1}, {2, 8, 6}}]

expr /. List -> h

h[h[h[7, 0, 8], h[2, 1, 5]], h[h[8, 0, 6], h[7, 2, 1]], h[h[0, 6, 1], h[2, 8, 6]]]

This head replacement can be used, for example, to sort all lists:

expr /. List -> Composition[Sort, List]

{{{0, 1, 6}, {2, 6, 8}}, {{0, 6, 8}, {1, 2, 7}}, {{0, 7, 8}, {1, 2, 5}}}
Improve this answer
$\endgroup$
7
  • $\begingroup$ I really appreciate the links you provided in your answer. I think I now know ReplaceAll scans an expression. I'm still confused about how it replaces its matches. For example h[h[u, h], h] /. x : head_[arg__] /; Print[x] :> x finds all heads h, yet h[h[u, h], h] /. h[arg__] :> k[arg] only replaces the outermost h. @mfvonh mentions in his comment that "ReplaceAll "quits" because it replaces the whole expr and doesn't test the new part". If that's the case, then why would h[h[u, h], h] /. h :> k even though when any h is replaced, the expressions would also change. $\endgroup$
    – seismatica
    Jul 28, 2014 at 16:51
  • $\begingroup$ @seismatica I'll address those questions in an addendum. Give me a few minutes. $\endgroup$
    – Mr.Wizard
    Jul 28, 2014 at 16:53
  • $\begingroup$ @seismatica Done. It took longer than expected but I think it was worth it. $\endgroup$
    – Mr.Wizard
    Jul 28, 2014 at 17:07
  • 1
    $\begingroup$ @seismatica Actually that does work, you just need to control grouping: expr /. List :> (Sort[List[##]] &). That is partly why I used Composition. :-) By the way, in v10 we can write: expr /. List -> Sort@*List $\endgroup$
    – Mr.Wizard
    Jul 28, 2014 at 18:01
  • 1
    $\begingroup$ @seismatica The reps slip through my fingers! =:o $\endgroup$
    – Mr.Wizard
    Jul 28, 2014 at 18:08

Your Answer

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

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