# Subtle order-of-evaluation issues when pattern-matching with attributes

Related question concerning unrolling the tests that are shown below:

Big and Little surprises when unrolling tests of pattern-matching and attributes

Questions researched before posting this one:

Orderless pattern matching

Combinations of multiple matching patterns

What has changed in pattern matching functions with the Orderless attribute?

Transformation rule for arbitrary number of argument expressions

Pattern does not match with Orderless head

In an attempt to understand pattern-matching better, I tried some exhaustive testing of a certain substitution rule under all seven combinations of attributes, leaving out the null case of no attributes:

In[1]:= allAtts =
Flatten[Table[
Union[Sort /@
Permutations[{Flat, Orderless, OneIdentity}, {i}]], {i, 3}], 1]
Out[1]= {{Flat}, {OneIdentity}, {Orderless}, {Flat, OneIdentity}, {Flat,
Orderless}, {OneIdentity, Orderless}, {Flat, OneIdentity,
Orderless}}


The substitution rule attempts to match the pattern eqv[x_, y_] against the input eqv[p, q, r] to see what gets bound to x and y for each combination of attributes.

In the first test, I define the substitution before setting the attributes. After some manual prettification of the output:

In[2]:= Table[Module[{e = (eqv[p, q, r] /. {eqv[x_, y_] :> {x, y}})},
ClearAll[eqv];
SetAttributes[eqv, j];
{j, First@e, Rest@e}],
{j, allAtts}]
Out[2]= {{{Flat},                         p, eqv[q, r]},
{{OneIdentity},                  eqv[p], {eqv[q, r]}},
{{Orderless},                    p, eqv[q, r]},
{{Flat, OneIdentity},            p, eqv[q, r]},
{{Flat, Orderless},              p, {eqv[q, r]}},
{{OneIdentity, Orderless},       q, {eqv[p, r]}},
{{Flat, OneIdentity, Orderless}, p, eqv[q, r]}}


The results are reasonable, plausible, interpretable.

In a second test (not-unrolled; see cited question above), I set the attributes before defining the substitution rule. The results are subtly different.

In[3]:= Table[Module[{e},
ClearAll[eqv];
SetAttributes[eqv, j];
e = (eqv[p, q, r] /. {eqv[x_, y_] :> {x, y}});
{j, First@e, Rest@e}],
{j, allAtts}]
Out[3]= {{{Flat},                         eqv[p], {eqv[q, r]}}, (* difft *)
{{OneIdentity},                  p, eqv[q, r]},        (* difft *)
{{Orderless},                    p, eqv[q, r]},
{{Flat, OneIdentity},            p, {eqv[q, r]}},      (* difft *)
{{Flat, Orderless},              q, {eqv[p, r]}},      (* difft *)
{{OneIdentity, Orderless},       p, eqv[q, r]},        (* difft *)
{{Flat, OneIdentity, Orderless}, p, {eqv[q, r]}}}      (* difft *)


My questions are:

1. Why, exactly, are there such differences? I understand that order-of-evaluation matters quite a bit, in general, in Mathematica, but it's hard for me to understand these particular differences. Details follow in the rest of my questions:

2. In the first test, with Flat alone, why do I get (a) p wrapped in eqv, i.e., eqv[p] and eqv[q, r] wrapped in List, when I set attributes before defining the substitution rule?

3. In the second test, for OneIdentity, alone, when attributes are set before the substitution rule is defined, do I get the same results as for Flat, alone, when the substitution rule is defined before the attributes are set? In other words, for the two orders of attributes-setttings versus rule-defining, are the results for Flat alone and OneIdentity alone swapped?

4. In the fourth test, for {Flat, OneIdentity}, why do I get no wrapping with List for the second substitution (for y) when the substitution rule is defined before the attributes are set, and yes wrapping with List when the attributes are set before the substitution rule is defined?

5. In the fifth test, for {Flat, Orderless}, why do I get p for x when the substitution rule is defined before attributes are set, and q for x when the attributes are set before the substitution rule is defined?

6. In the sixth test, for {OneIdentity, Orderless}, there are two differences between the two conditions (substitution rule defined before attributes set, and attributes set before substitution rule defined). The first difference (a) is that I get q for x in the first condition and p for x in the second condition. The second difference (b) is that I get List wrapping in the first condition and no List wrapping in the second condition.

EDIT: I missed the last difference in the original, and finding it gave me an opportunity to ask the sharpest questions:

1. In the seventh test, for all three attributes, I get an extra List wrapping in the output in the second condition, attributes-set before substitution-defined. Why is that? Should I have been able to predict it knowing just the conditions? By what reasoning?

I apologize for the length and complexity of this question, but I made it as short and as simple as I know how to. This question reveals that I don't know nearly as much as I thought I did about pattern-matching and attributes. Perhaps after I learn more from you-all, a much simpler form of the essential question --- hiding in here somewhere I hope --- will emerge.

• First, it makes no sense to set attributes after doing the replacement. Second, the only time the replacement rule will fire is when Flat is one of the attributes. If you include e in your output, you will see that the replacement only did something when Flat was one of the attributes. – Carl Woll Oct 8 '18 at 18:59

Carl Woll's comment turned the lights on for me and cleared the fog. There are no matches when there is no Flat. That observation also clears up the related question Big and Little surprises when unrolling tests of pattern-matching and attributes.

Here are the only tests that make sense out of the above, now unrolled.

In[16]:= Module[{}, ClearAll[eqv]; SetAttributes[eqv, {Flat}];
eqv[p, q, r] /. {eqv[x_, y_] :> {x, y}}]

Out[16]= {eqv[p], eqv[q, r]}

In[17]:= Module[{}, ClearAll[eqv];
SetAttributes[eqv, {Flat, OneIdentity}];
eqv[p, q, r] /. {eqv[x_, y_] :> {x, y}}]

Out[17]= {p, eqv[q, r]}

In[18]:= Module[{}, ClearAll[eqv];
SetAttributes[eqv, {Flat, Orderless}];
eqv[p, q, r] /. {eqv[x_, y_] :> {x, y}}]

Out[18]= {q, eqv[p, r]}

In[19]:= Module[{}, ClearAll[eqv];
SetAttributes[eqv, {Flat, OneIdentity, Orderless}];
eqv[p, q, r] /. {eqv[x_, y_] :> {x, y}}]

Out[19]= {p, eqv[q, r]}


The answer for {Flat, Orderless} seems puzzling. Usually, Mathematica sorts symbolic constants alphabetically and minimizes nesting, leading us to expect {p,eqv[q,r}. There are an unbounded number of correct answers, all equivalent under these attributes, however, any of which would be acceptable. Here are just a few:

In[54]:= ClearAll[eqv]; SetAttributes[eqv, {Flat, Orderless}];
eqv[eqv[p], eqv[r, q]] === eqv[eqv[q], eqv[p, r]] ===
eqv[eqv[q], eqv[r, p]] === eqv[eqv[q], eqv[r, p]] ===
eqv[eqv[r], eqv[p, q]] === eqv[eqv[r], eqv[q, p]] ===
eqv[p, eqv[r, q]] === eqv[q, eqv[p, r]] ===
eqv[eqv[eqv[p]], eqv[q, r]] === eqv[eqv[p], q, r]

Out[55]= True


Indeed, even the result for Flat alone has many correct answers:

In[58]:= ClearAll[eqv]; SetAttributes[eqv, {Flat}];
eqv[eqv[p], eqv[q, r]] === eqv[p, eqv[q, r]] ===
eqv[eqv[eqv[p]], eqv[q, r]] === eqv[eqv[p], q, r]

Out[59]= True

• You can use ReplaceList to show all possible replacements. It is an open question as to why the {Flat,Orderless} case is not giving the first element fro the ReplaceList result. – Daniel Lichtblau Oct 9 '18 at 0:51