Orderless and Sequence

I just ran into the following subtlety.

Let us consider a function f with attribute Orderless.

Attributes[f]={Orderless};


For pattern matching, the consequence of this attribute is that when we have an expression with head f, any ordering of the arguments is tested. That can be seen in the following result:

ReplaceList[ f[a,b,c], f[x_,y_, z_] :> {x,y,z} ]

(* {{a,b,c},{a,c,b},{b,a,c},{b,c,a},{c,a,b},{c,b,a}} *)


I would have expected the same result from the next command, where in the rule I catch the three arguments of f in a BlankSequence, thereby placing a Sequence expression in the list at the right hand side:

 ReplaceList[ f[a,b,c], f[x__] :> {x} ]

(* {{a,b,c}} *)


It only gives one result! Likely, I overlooked something simple, but I fail to see a good explanation. Why does this not work?

Here is how I make sense of this behavior. When a function that appears in a pattern has attribute Orderless, the pattern-matcher must generate all possible permutations of its argument sequence before trying to match these patterns.

Refer to a simple example expression such as a /. b -> c: in a nutshell, as Fred mentioned in his comment below, I contend that the attribute Orderless causes the system to generate possible alternatives for the b expression, rather than for a.

When the argument sequence of your orderless f function contains more than one argument, then multiple permutations are generated. The specification f[x_, y_, z_] -> {x, y, z} in the second argument of ReplaceList can be thought of as equivalent to the following "expanded form":

{f[x_, y_, z_] -> {x, y, z}, f[x_, z_, y_] -> {x, y, z}, f[y_, x_, z_] -> {x, y, z},
f[y_, z_, x_] -> {x, y, z}, f[z_, x_, y_] -> {x, y, z}, f[z_, y_, x_] -> {x, y, z}}


Each one of those patterns matches f[a, b, c] in the first argument of ReplaceList, hence the multiple results.

However, when the pattern specified in the second argument of ReplaceList contains only one argument, then there are no permutations to account for, so only one "equivalent pattern" is considered, which matches once.

To clarify my point, here is a helper function that approximates my vision of what the pattern matcher is doing for orderless functions. Note that here we use a regular, non-orderless g function, and simulate orderless behavior explicitly.

Clear[generateOrderlessPatterns]
Attributes[g] = {};

generateOrderlessPatterns[functiontoapply_, list_, patterntype_] :=
Table[
functiontoapply[Sequence @@ (Pattern[#, patterntype] & /@ i)] -> list,
{i, Permutations[list]}
]


We can then generate "orderless-style" patterns for the non-orderless g function:

generateOrderlessPatterns[g, {x, y, z}, Blank[]]

(* Out:
{g[x_, y_, z_] -> {x, y, z}, g[x_, z_, y_] -> {x, y, z}, g[y_, x_, z_] -> {x, y, z},
g[y_, z_, x_] -> {x, y, z}, g[z_, x_, y_] -> {x, y, z}, g[z_, y_, x_] -> {x, y, z}}
*)


On the other hand, if we use a BlankSequence pattern, we obtain:

generateOrderlessPatterns[g, {x}, BlankSequence[]]

(* Out: {g[x__] -> {x}} *)


Using these patterns in ReplaceList emulates the Orderless behavior of f:

ReplaceList[g[a, b, c], generateOrderlessPatterns[g, {x, y, z}, Blank[]]]

(* Out:
{{a, b, c}, {a, c, b}, {b, a, c}, {c, a, b}, {b, c, a}, {c, b, a}}
*)

ReplaceList[g[a, b, c], generateOrderlessPatterns[g, {x}, BlankSequence[]]]

(* Out: {{a, b, c}} *)

• This seems to me a very convincing description of how substitution with orderless an function could have been implemented. Many thanks. Roughly speaking, your idea is that in a /. b->c, the attribute Orderless is used to create alternatives for b. That explains why using BlankSequence does not work. On the other hand, the fact that BlankSequence does not work seems contra intuitive to me, the more since I think that it is possible to implement orderless by constructing alternatives for a, just as is done (I think) with the attribute Flat. Then it would have worked. – Fred Simons Nov 30 '15 at 18:54
• @Fred 1. "your idea is that in a /. b -> c, the attribute Orderless is used to create alternatives for b": That is not only correct, it is actually a nicer and clearer summary than I have in my current answer, so I think I'll add it in if you don't mind. 2. I agree that the behavior with BlankSequence may be counter-intuitive; on the other hand, it makes sense to me to try and generate alternatives on the simpler b expression rather than on a since, given the context of pattern matching, on average it can be expected that a is likely to be more complicated than b. – MarcoB Nov 30 '15 at 19:07
• This is a nice theory, but it doesn't seem to be the whole story. Try ReplaceList[f[p, q, r], f[a__, b__] :> {a}] for an orderless f. This gives 6 results ({{p}, {q}, {r}, {p, q}, {p, r}, {q, r}}), whereas an equivalent usage of your generateOrderlessPatterns gives only 4. In particular, the results {q} and {p, r} from my snippet cannot be matched without doing some rearranging on the left-hand side as well. At the same time it doesn't do any rearranging within the matches of a given pattern sequence (otherwise there would be 12 results). – Martin Ender Jan 10 '17 at 11:08
• After some discussion in chat, we've narrowed this down further. It seems that the pattern matcher does try every possible assignment of sequences to elements (even if that requires reordering the left-hand side), but it will only attempt assignments where each of the sequences itself is ordered. Compare MatchQ[f[1, 2, 3], f[a__, b__] /; {b} == {1, 3}] and MatchQ[f[1, 2, 3], f[a__, b__] /; {b} == {3, 1}] for orderless f (they yield True and False respectively). Replacing b__ with 3, 1 and dropping the condition gives True again. – Martin Ender Jan 10 '17 at 14:54

Because of the Orderless attribute of f, the function ReplaceList always evaluates with the arguments of f arranged in the canonical order. For instance looking at the Trace of the next expression, we see that

ReplaceList[ f[b, c, a], f[z_, y_, x_] :> {x, y, z} ]


is re-ordered to

ReplaceList[ f[a, b, c], f[x_, y_, z_] :> {x, y, z} ]


before the internal definition of ReplaceList is used. The replacement rule f[x_, y_, z_] :> {x, y, z} is then applied to f[a, b, c] in all possible ways, as noted in the documentation of ReplaceList. Since f is Orderless, these "all possible ways" are all possible permutations of f[x_, y_, z_], as mentioned by MarcoB in its answer.

These comments should also explain why the following two lines return the same output list of length 1:

ReplaceList[f[a, b, c], f[x___] :> {x}]
ReplaceList[f[b, c, a], f[x___] :> {x}]
(* {{a, b, c}} *)


The re-ordering of the arguments of f happens before ReplaceList evaluates, so ReplaceList will evaluate with f[a, b, c] in both cases and apply the rule(s) to this expression. Now, the only way to apply the rule is f[x___] :> {x}. (There are no permutation in this situation as written by MarcoB.)

As a last remark, one may look at the evaluation of

ReplaceList[ f[b, c, a], f[y_, x_, z_] :> f[z, y, x] ]


to notice that only the permutations of the pattern expression itself are considered, and not of the whole rule. It would have otherwise resulted in an output list of greater length.