# ReplaceRepeated seemingly omits some rules

Is there a simple way in Mathematica to prevent rule reordering? Let me give an example:

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


though

a -> b /. {b -> c}
(* a -> c *)


works fine, of course. (I think that) Mathematica has determined that the second rule in expression 1 is more specific than the first rule and so has ordered it first. But, in the ReplaceRepeated, Mathematica now never checks the first rule. I realize that there are ways to rewrite this so that it works fine but is there a simple way to tell Mathematica not to reorder the rules? It seems like there should be.

-

As István describes this has to do with the traversal direction of //.. ReplaceAll and by extension ReplaceRepeated are very unusual in the context of Mathematica in that they perform a depth-first preorder traversal, whereas nearly all other functions perform a depth-first postorder traversal. Since it is the latter that you want here you merely need to use Replace instead of ReplaceRepeated (with the correct levelspec), and you can complete the behavior with FixedPoint.

postorderReplaceRepeated[expr_, rules_] :=
FixedPoint[Replace[#, rules, {0, -1}, Heads->True] &, expr]

postorderReplaceRepeated[a -> b, {b -> c, (x_ -> y_) :> (x -> Expand[y])}]

a -> c


(Note: be sure to use RuleDelayed (short form :>) when working with named patterns on the right-hand side unless you specifically know otherwise.)

-
Wow. Very nice. I wasn't aware of the intricacies of tree traversal order, in particular that Replace with all levels included and applied repeatedly is different from ReplaceAll (of course, I wish the Mathematica documentation stated some of this ;-( ). István, of course, got the reason for the problem correct and offered useful suggestions, but your method does essentially fix it. Thanks. –  jondaman21 Dec 12 '13 at 11:24
Hi. I added Heads->True to the options for Replace, since I think this better mimics the behavior of ReplaceRepeated. Also, do you mind explaining what the levelspec of {0,-1} does vs. {0,Infinity}? I don't understand (including from the documentation) what the -1 level spec refers to. –  jondaman21 Dec 12 '13 at 11:32
@jondaman21 Good catch on Heads -> True! Levels are described and illustrated by several people here -- I like both David's and Rahul's graphics myself. In this case {0, -1} and {0, Infinity} should behave the same; the first is simply faster to write. –  Mr.Wizard Dec 12 '13 at 20:31

There is no reordering: ReplaceRepeated simply starts replacement from the outside of the expression. For example here the result is not f[g[g[1]]] but:

 f[f[f[1]]] //. f[f[x_]] :> g[g[x]]   (*   ==> g[g[f[1]]] *)


So in your case, the first rule that is matched is the second one, which happens to be more general (but it has nothing to do with evaluation order). Print statements make it explicit that indeed the first rule is not tried at all:

a -> b //. {b -> (Print[1]; c), (x_ -> y_) :> (x -> (Print[2]; Expand[y]))}

During evaluation of In[12]:= 2

a -> b


There are at least two ways to overcome this. First, you can apply rules repeatedly from the inside (deepest-level-first). Giving explicit (reversed) level specifications to Replace inside Fold will do the replacements from inside->out.

expr = a -> b;
rules = {b :> (Print[1]; c), (x_ -> y_) :> (x -> (Print[2]; Expand[y]))};

Fold[Replace[#1, rules, {#2}] &, expr, Reverse@Range[0, Depth@expr]]

During evaluation of In[83]:= 1

During evaluation of In[83]:= 2

a -> c


Other way is to specify an explicit order of the rules to be applied:

Fold[ReplaceRepeated, expr, rules]

During evaluation of In[16]:= 1

During evaluation of In[16]:= 2

a -> c


Note that the two approaches are not identical: the second one might do repeated replacements per iteration of Fold, while the first one only tries each rule once per iteration of Fold.

-