pattern matching - 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?

Answer

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}} *)