Why does the name of a pattern affect the result of a transformation rule?

Question

I was playing a little dirty, trying to get a template for defining a Curl[] operator.

I wrote the following rule, which I knew was going to spit out a few errors, because all symbols there (including the lists), were undefined:

Cross[{d[1], d[2], d[3]}, {2, 3, 4}] /. Times[a_, b_] -> b[[a]]

Notwithstanding the errors, the result I got was what I wanted:

(* {d[2][[4]] + d[3][[-3]], d[1][[-4]] + d[3][[2]], d[1][[3]] + d[2][[-2]]} *)

with a few more replacements, you can almost see the Curl[] operator materializing.

Sadly, I forgot that the symbol a was already in use in may main .nb, so I changed it to c. Look:

Cross[{d[1], d[2], d[3]}, {2, 3, 4}] /. Times[c_, b_] -> b[[c]]

But now the results are completely different!

(* {(-3)[[d[3]]] + 4[[d[2]]], (-4)[[d[1]]] + 2[[d[3]]], (-2)[[d[2]]] + 3[[d[1]]]} *)

Wow!

I Traced the evaluation, and could easily find out where the both processes started to differ, but I couldn't understand why.

Any ideas?

Answer 1

Just my little cent (yeah, cent is uncountable, there are too much of them around, so what)

Orderless (quite similarly to Flat) not only affects the automatic reordering of arguments. It also affects the pattern matching.

In here, both things are responsible for the behaviour. Not both together, but both by themselves. @R.M has already explained how the reordering of the patterns can ruin the party.

As to the second issue, when the pattern matcher is faced with matching an expression with an Orderless head, it knows it will have to check all combinations of orders of the patterns (until it finds one). So, for example

Hold[2 "a"] /. Hold[i_String j_Integer] :> {i, j}

{"a", 2}

A nice application of this behaviour is in @Mr.Wizard's answer

So, no matter the actual stored ordering of the patterns, it just gets ignored when matching

In conclusion, I support @R.M's advice on not to rely ever on the ordering of arguments of an Orderless head

Answer 2

This is due to the Orderless attribute of Times. When you write Times[c_, b_], it automatically gets reordered to Times[b_, c_] even before any of the rules have been read. The reordering is in the sense of OrderedQ. Compare:

OrderedQ[{Pattern[b, Blank[]], Pattern[c, Blank[]]}]
(* True *)
OrderedQ[{Pattern[c, Blank[]], Pattern[b, Blank[]]}]
(* False *)

Once you realize that, you can begin to see why b[[c]] wouldn't give the right answer.

If you compare the two results closely, you'll see that each term is just flipped inside out (loosely speaking). i.e., d[2][[4]] becomes 4[[d[2]]], which is in accordance with b and c being flipped by the reordering. To further confirm this is the case, change the rule to Times[c_, b_] -> c[[b]] and you'll get the same answer as in the first case.

In general, it is probably not a good idea to use rely on the order of arguments in an orderless function for further processing/rules unless if the order doesn't matter in the latter case too (e.g. changing Times to Plus).