Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
    
Thank you! Do you know why Replace work but not ReplaceAll? –  seismatica Jul 28 at 2:34
1  
@seismatica see my update. –  RunnyKine Jul 28 at 2:44
    
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? –  seismatica Jul 28 at 3:04
2  
@seismatica It should touch the inside heads in that case. You could do that with (head: Except[newHead])[arg__] to avoid infinite recursion. –  mfvonh Jul 28 at 3:08
2  
@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 –  mfvonh Jul 28 at 12:16

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 never 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}}}
share|improve this answer
    
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. –  seismatica Jul 28 at 16:51
    
@seismatica I'll address those questions in an addendum. Give me a few minutes. –  Mr.Wizard Jul 28 at 16:53
    
@seismatica Done. It took longer than expected but I think it was worth it. –  Mr.Wizard Jul 28 at 17:07
1  
@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 –  Mr.Wizard Jul 28 at 18:01
1  
@seismatica The reps slip through my fingers! =:o –  Mr.Wizard Jul 28 at 18:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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