ReplaceRepeated seemingly omits some rules

Question

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.

Answer 1

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.)

Answer 2

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.