# ReplaceAll is not working correctly

The line of code

-E^(-I k) x /. {-x -> -x, -E^(-I k) x -> -E^(I k) x}


is not properly replacing the exponential of (-I k) with the exponential of (I k), as it should. The trivial replacement -x -> -x (which is not performed anyway) seems to be breaking the second replacement - if I exchange the order of the replacements, I get the correct answer. Can anyone help?

I tried FullForm on the expression -E^(-I k) x, and it gives

Times[-1, Power[E, Times[Complex[0, -1], k]], x].


Edit: This issue has nothing to do with complex numbers - the exact same problem occurs if you remove all of the I's. The first replacement is being performed, but the second one should be as well, because it does not apply to either the previous part that was replaced or to a subpart. For example, the line

x Exp[y] /. {x -> a, x Exp[y] -> b}


correctly evaluates to b. I believe that the fact that the second replacement is not being performed is a bug in Mathematica.

• A look at the FullForm[] of the expression you're trying to change will prove illuminating. Commented Jul 14, 2015 at 21:26
• Also note the Details section in ref/ReplaceAll: "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. " Commented Jul 14, 2015 at 21:35
• Take a look at this answer that deals with possible difficulties in writing replacement rules including the imaginary unit I. I think that should also clarify what @Guesswho was hinting at. Commented Jul 14, 2015 at 22:43
• possible duplicate of Mathematica does not replace \‌[ImaginaryI] inside Hold Commented Jul 14, 2015 at 22:44
• Related: (18060). And I think these Q&A's would be useful to read, even if they do not directly apply here: (22948), (25538), (57361), Commented Jul 15, 2015 at 6:46

I think this may be what ilian is driving at, but I couldn't be sure in first answer. I thought that some elaboration would be helpful in any case. The behavior of flat and orderless functions in patterns is explained in tutorial/FlatAndOrderlessFunctions. While Orderless is significant here, I think it is the attribute Flat that one needs pay particular attention to.

Consider these examples:

2 x y /. {2 x -> a, 2 x y -> b}
(*  a y  *)

2 x y /. {x -> a, 2 x y -> b}
(*  b  *)


When we look at the FullForm, it is important to pay attention not just to 2 x y, but to the patterns that are potential matches, 2 x, 2 x y and x.

ReplaceAll[
Times[2, x, y],
List[
Rule[Times[2, x], a],
Rule[Times[2, x, y], b]]]

ReplaceAll[
Times[2, x, y],
List[
Rule[x, a],
Rule[Times[2, x, y], b]]]


In the first case, there are four five possible expressions to match: Times[2, x, y] (first), then the part Times (the Head or part 0), and then parts 1 through 3, that is 2, x, y in any order. Because Times is Flat, the pattern Times[2, x] can be applied to the first one, Times[2, x, y], matching the subexpression as if the whole were (2 x) y. From the tutorial:

However, if you have a flat function, it is sometimes possible to apply transformation rules even though not all the arguments are covered.

In[13]:= a + b + c /. a + c -> p

Out[13]= b + p


But since Times[2, x, y] was the whole expression, there is nothing left to apply the rules to. Note this explains why y is not replaced in this case, too:

2 x y /. {2 x -> a, y -> b}
(*  a y  *)


In the second example above, again a rule may be applied to Times[2, x, y], this time 2 x y -> b. Again ReplaceAll stops after this for the same reason.

Finally, both rules are applied below in

2 x y /. {x -> a, y -> b}
(*  2 a b  *)


because nothing can be applied to Times[2, x, y], but x -> a and y -> b can each be applied to one of the parts of the expression.

Update - I lost my Head (see above, too)

Examples related to the head of the expression, Times:

2 x y /. {Times -> List, 2 x -> a}   (* the whole transformed, part Times not replaced *)
(*  a y  *)

2 x y /. {Times -> List, x -> a}     (* Head and subpart transformed *)
(*  {2, a, y}  *)

• This is a very helpful explanation! So if I understand correctly, by simply looking at your two example commands, we could not predict which of the two replacements Mathematica would choose to perform: it depends on whether or not each specific command is one of the (vaguely defined) cases where "it is sometimes possible" to treat one of the smaller substitutions as acting on the larger expression. Correct? Commented Jul 15, 2015 at 5:37
• But here's another weird thing: if you run "ReplaceList" on your two examples rather than "ReplaceAll", both examples give that the only possible replacement is replacing the entire expression by b. For your first example, why is Mathematica choosing to perform a replacement that isn't even on the list of possible replacements given by ReplaceList? Commented Jul 15, 2015 at 5:45
• @tparker (1) Sometimes principles aren't stated with perfect clarity and precision but might still be inferred (often only with experience). In this case, one has to come to understanding of how functions (e.g. Times) that are Flat and Orderless are used in pattern-matching. First replacement is tried on the whole, and there are several ways a pattern might match, Times[2,x,y], Times[Times[2,x],y], Times[Times[2,y],x] and Times[Times[x,y],2] (up to reordering). If one understands that (& maybe I'm not clear enough yet), I think one can predict which replacement will be applied... Commented Jul 15, 2015 at 18:46
• ...One tricky bit of wording that is not made clear in the docs is when a replacement can be "applied" and when a pattern "matches." These are not the same. When ReplaceAll tries to apply a replacement, it goes through all ways of arranging a flat, orderless function. It will replace a subpart that is created by rearranging, so to speak. I'm intentionally hedging because 2*x is not a subpart of 2*x*y. So when ReplaceAll replaces 2*x by a, it has applied a rule to the whole expression, even though it did not match the whole expression... Commented Jul 15, 2015 at 18:55
• @tparker (2) ReplaceList (seems to) only make replacements that match the whole expression. This distinction does not seem very clear in docs, although perhaps it is explained somewhere. Replace works the same way. Commented Jul 15, 2015 at 18:58

Note that Times has the Flat and Orderless attributes, so the first replacement actually is performed.

Both of the following ReplaceAll results are correct:

-E^-y x /. {Times[-1, x] -> -x, -E^-y x -> -E^y x}
(* -E^-y x *)


where the whole expression is considered to match the first rule because of the Flat attribute, and the second rule is not applied similarly to this example

 SetAttributes[f, Flat];
f[a, b, c] /. {f[a, b] -> x, f[a, b, c] -> y}
(* f[x, c] *)


However, if the order is switched,

-E^-y x /. {-E^-y x -> -E^y x, Times[-1, x] -> -x}
(* -E^y x *)


where the whole expression is transformed by the first rule, similarly to

 f[a, b, c] /. {f[a, b, c] -> y, f[a, b] -> x}
(* y *)

• I agree with you that the "the second rule does not apply to the second part" E^(-y). But it does apply to the entire expression as a whole, which is higher up in the FullForm[] tree. Once a part has had a rule performed on it, no further rules can be performed on that part or on a subpart. But further rules can be performed on "superparts" - parts that are higher up in the tree - so your answer doesn't explain why the second rule isn't performed on the entire expression after the first rule is performed. Commented Jul 15, 2015 at 5:53
• Third time is the charm (?) Commented Jul 15, 2015 at 6:22
• Okay, now I understand. The part I was missing was that Times's attribute Flat means that the first rule actually applies to the entire expression, not just the part Times[-1, x]. I still have the same two questions below Michael E2's answer: (1) Do Flat functions always treat rules that apply to more than one of, but not all of, their arguments as transforming the entire function, or only "sometimes", as the tutorial says? (2) In his first example, why doesn't ReplaceList say that the first rule can apply to the whole expression? Commented Jul 15, 2015 at 8:00

The other answers have addressed the question well, but I'd like to try to illustrate one of the confusing points.

Suppose we have the replacement operation

x y z /. {x -> a, x y -> b, x y z -> c}


Without a detailed understanding of the pattern matcher, it may be difficult to guess which rule will be applied. Knowing that the rules are applied in order, one might guess that the first rule will be applied, or knowing that the entire expression is considered first, followed by the subexpressions, one might guess that the last rule will be applied. In fact, the result is

b z


meaning that the second rule is applied.

We can print out the order that subexpressions are considered with

x y z /. {x_?Print -> Null};


x y z

Times

x

y

z

So the whole expression is considered first, followed by the head and then the arguments in order. But in our original replacement rules, the second and third patterns have head Times, which has attributes Flat and Orderless. So when the entire expression, which has head Times, is considered, the pattern matcher tries various permutations of the arguments. What order are the permutations tried in? We can see this for our original rules with

x y z /. {
x_Symbol /; Print[x] -> Null,
x_Symbol y_Symbol /; Print[x, y] -> Null,
x_Symbol y_Symbol z_Symbol /; Print[x, y, z] -> Null
};


xy

yx

xz

zx

yz

zy

xyz

xzy

yxz

yzx

zxy

zyx

Times

x

y

z

First the entire expression is considered, and the rules are tried in order. The pattern from the first rule doesn't have head Times, so it doesn't match. The pattern from the second rule has head Times and two arguments (with head Symbol) so all combinations of two arguments from the expression are tried. Then the third rule is tried, which has three arguments, so all combinations of three arguments are tried. Then the matcher moves on to the subexpressions, which match the first rule.

Incidentally, we can get the rule x -> a to match in the first step, when the entire expression is considered, by giving it the head Times, like so:

x y z /. {HoldPattern@Times[x] -> a, x y -> b, x y z -> c}

(* a y z *)


Now it takes precedence over the second rule.

Some insight can be obtained by using Trace.

Trace[-E^(-I k) x /. {-x -> -x, -E^(-I k) x -> -E^(I k) x}]//InputForm


The final few lines of the resulting lengthy expression are

(* HoldForm[-(x/E^(I*k)) /. {-x -> -x, -(x/E^(I*k)) -> -(E^(I*k)*x)}],
HoldForm[-x/E^(I*k)], HoldForm[-x/E^(I*k)], HoldForm[-(x/E^(I*k))] *)


We see that the first rule, -x -> -x. converts HoldForm[-(x/E^(I*k)) into HoldForm[-x/E^(I*k)], which is not the same as the second rule, -(x/E^(I*k)) -> -(E^(I*k)*x), so the second rule has no effect.

Consider, next, the same expression with the two rules reversed in order.

Trace[-E^(-I k) x /. {-E^(-I k) x -> -E^(I k) x, -x -> -x}]//InputForm


Again, focus on the final few lines of output.

(* HoldForm[-(x/E^(I*k)) /. {-(x/E^(I*k)) -> -(E^(I*k)*x), -x -> -x}],
HoldForm[-(E^(I*k)*x)] *)


Here, the first rule, -(x/E^(I*k)) -> -(E^(I*k)*x) matches and converts HoldForm[-(x/E^(I*k)) into HoldForm[-(E^(I*k)*x)]. The second rule has no effect.

Conclusion first：I highly believe there are some bugs in the cases when ReplaceAll(/.) is applied to a function which is Flat or(and) Orderless.

----------Below are investigation and explanation----------

First let me explain what the "detection rules" given by Simon do. As shown in documentation, when replacements are applied to flat or(and) Orderless (also OneIndentiy) functions, it tries to transform that function into different "equivalent forms". For example x y z(Times[x,y,z]) is equivalent to x (y z) (Times[x,Times[y,z]]),(x y) z (Times[Times[x,y],z]) , x z y, etc. So we want to know what exactly the pattern is matched to. However, Trace can't do the job. So we need to utilize Print's power. That is, use pattern in the lhs(left-hand side) of rules, and put it into Print as arguments. By doing so, as long as lhs pattern matches any equivalent form, it shows. However, we need to keep it continue until it exhausts all the equivalent forms. We can do this because Print returns Null, which is always not a True. ReplaceAll gets deceived and keep going.

Besides, a equivalent form is "effective" if and only if all the parameters in patterns get different values. For example, if x y z is matched by x_, then x (y z) will not be considered since after evaluation it is still x y z.

To investigate replacement on x y z is too complicated, because it's simutaneously Flat, Orderless and OneIdentity. Let's isolate each attribute to see what they individually bring about. But just when it comes to Flat, lots of problems show.

First a simple function h:

h[x, y, z] /. {
x_ /; Print[FullForm@f[x]] -> Null,
h[x_, y_] /; Print[FullForm@f[x, y]] -> Null,
h[x_, y_, z_] /; Print[FullForm@f[x, y, z]] -> Null};
(*
f[h[x,y,z]]
f[x,y,z]
f[h]
f[x]
f[y]
f[z]
*)


Let's explain why. First consider the 0 level(expression itself) to match the 1st rule, this is the first line. Then try matching the 2rd rule, fails. Then the 3rd, succeed. This is the third line. So far, the 0 level is over. Next is to search level-1(subexpression). First comes expr[[0]], that is h (I believe it's special to check the head itself in Replacement), thus give out f[h]. Then expr[[1]], which is x, followed by y and z. Those are the last lines.

Everything is clear, good! But the second example will mess up everything!

Second, a Flat function g1:

SetAttributes[g1, Flat];
g1[x, y, z] /. {
x_ /; Print[FullForm@f[x]] -> Null,
g1[x_, y_] /; Print[FullForm@f[x, y]] -> Null,
g1[x_, y_, z_] /; Print[FullForm@f[x, y, z]] -> Null};
(*
f[g1[x,y,z]]
f[g1[x],g1[y,z]]
f[g1[x,y],g1[z]]
f[x,g1[y,z]]
f[g1[x,y],z]
f[g1[x],g1[y]]
f[x,y]
f[g1[y],g1[z]]
f[y,z]
f[g1[x],g1[y],g1[z]]
f[x,y,z]
f[g1]
f[x]
f[y]
f[z]*)


Pay attention that now we have Flat attribute. It introduces the third degree of freedom when iterating, the equivalent form. Now there are 3 different iterative levels——rules, equivalent form, and level of the expr.

The first line f[g1[x,y,z]] is easy, exactly the same as in the first example (Level-0, first rule, (first form)). Since Print pretends the match to be disqualified, it tries to find the equivalent form to match the first rule. Then g1[x,y,z] becomes g1[g1[x,y,z]], which matches the (lhs of the) first rule. However as pointed out before, it's exactly equals to g1[x,y,z]. In the essence, pattern x_ gets the same value, so it's ineffective. The same is true for other equivalent form of level-0, such as g1[g1[x],g1[y],g1[z]]. They all comes out as the 1st line.

In level-0, the first rule is exhausted, now comes the second rule. Trying to transform, and get several matches, which are the 2rd~5th lines.

However, the 6th line is in no ways able to be explained. Dive into the level-1 of g1[g1[x,y],z]? But why it didn't do this when we are dealing with the first rule, namely leading to outcomes as f[x],f[y],f[z].

In another way to show the problem, we can ask "why doesn't f[x,g1[y],g1[z]] come out? g1[x,g1[y],g1[z]] is also an equivalent form isn't it?"

You may say "OK maybe there is some problem with this. However it's such a stupid example that everyone knows when you try to replace x and x y z simultaneously, there is ambiguity that where x belong to. I won't do such replacement." Wow mate! How about this situation:

x y z /. {x -> a, y z -> b}


I know you want a b while it ridiculously gives b x. Got crazy already? (To see more example, you can try more symbols powered together (say x y z w/.{x -> a, f[y, z, w] -> b}`).)

Summary:

I've tried going through all the related documentation and google, no clear explanations found. Now I deeply believe it's a bug. To be more precisely, there is a bug when each lhs of the replacement rules will match arguments of a Flat(or maybe also Orderless) function.

The current makeshify calling to my mind is, in this situation, try to replace one at a time.