Pattern matching an expression involving Times

Question

I'm trying to write a Mathematica function that will format expressions according to my preferences, for example displaying (5 c x)/Sqrt[2] as 5/Sqrt[2] c xinstead. While attempting this I have come across some pattern matching behaviour that I don't understand, which reveals some holes in my understanding of the evaluation process.

As a simple example, consider the following:

Times[a, b, f[], c] /. Times[x__, f[], y__] :> {{x}, f[], {y}}

{{a}, f[], {b, c}}

I expected that this would output

{{a, b}, f[], {c}}

A Trace gives the following output:

Column@Trace[Times[a, b, f[], c] /. Times[x__, f[], y__] :> {{x}, f[], {y}}]

{a b f[] c,a b c f[]}

{{x__ f[] y__,f[] x__ y__},f[] x__ y__:>{{x},f[],{y}},f[] x__ y__:>{{x},f[],{y}}}

a b c f[]/. f[] x__ y__:>{{x},f[],{y}} 

{{a},f[],{b,c}}

Clearly Times is evaluating and shuffling its arguments to a standard form. I will obviously have to apply HoldForm or similar, but even at this stage I don't understand why the ReplaceAll as shown in the Trace outputs this result. (EDIT: To be clear, I don't understand why or how Mathematica has gotten a b c f[] to match f[] x__ y__, or why a is matched by x__ and b, c are matched by y__). What approach should I apply to understand why this is the result?

Next, I try again while holding expressions:

HoldForm[Times[a, b, f[], c]] /. HoldPattern[Times[x__, f[], y__]] :> {{x}, f[], {y}}

{{a},f[],{b,c}}

And I still get the undesired result. Here is the Trace:

Trace[HoldForm[Times[a, b, f[], c]] /. HoldPattern[Times[x__, f[], y__]] :> {{x}, f[], {y}}]

{HoldPattern[x__ f[] y__]:>{{x},f[],{y}},HoldPattern[x__ f[] y__]:>{{x},f[],{y}}}

a b f[] c/. HoldPattern[x__ f[] y__]:>{{x},f[],{y}}

{{a},f[],{b,c}}

Now it appears as if Times is not shuffling its arguments, but somehow along the way the b has still been matched by y__. What is happening under the hood here? And why is Trace not showing it?

Finally now I remembered Verbatim:

HoldForm[Times[a, b, f[], c]] /. Verbatim[Times][x__, f[], y__] :> {{x}, f[], {y}}

{{a,b},f[],{c}}

which gives the desired result. Why does Verbatim work better here than HoldPattern? I have been told before that Verbatim is for "escaping the pattern matcher", but the argument Times of Verbatim hardly seems like something that the pattern matcher should care about.

So to summarise:

• How do I understand what is happening under the hood when pattern matching with Times?

• Why did Verbatim work better than HoldPattern?

EDIT:

Thinking more about this line:

HoldForm[Times[a, b, f[], c]] /. HoldPattern[Times[x__, f[], y__]] :> {{x}, f[], {y}}

I don't understand how shuffling the arguments of Times[x__, f[], y__] could cause y__ to match b c, since b and c in the expression are separated by f[]. Is the pattern matcher able to shuffle the arguments of the expression even though it is contained in HoldForm?

Answer 1

Because of the Orderless property of Times, the following

Times[a, b, f[], c] /. Times[x__, f[], y__] :> {{x}, f[], {y}}

gets turned into

a b c f[]/. f[] x__ y__:>{{x},f[],{y}} 

through canonical ordering. Furthermore, the Orderless attribute of Times in the pattern means that "all possible orders of arguments are tried". Additionally, "If no explicit Shortest or Longest is given, ordinary expression patterns are normally effectively assumed to be Shortest[p]".

So the pattern matcher will shuffle f[] x__ y__ until the f[] gets to the end, whereupon x__ will match a as Shortest[x__] and y__ will match b c as Shortest[y__].

In the next example

HoldForm[Times[a, b, f[], c]] /. HoldPattern[Times[x__, f[], y__]] :> {{x}, f[], {y}}

the expression is held, and the pattern is held, but even though it does not evaluate, the pattern matcher still sees that Times is Orderless, and so all possible orders or arguments are tried, and the x__ and y__ patterns are still treated as Shortest. So the best match is still

{{a},f[],{b,c}}

When Verbatim is used:

HoldForm[Times[a, b, f[], c]] /. Verbatim[Times][x__, f[], y__] :> {{x}, f[], {y}}

the Times head is no longer "active", and so the pattern matcher will not consider any attributes of Times. The desired result is then obtained.

EDIT:

Here I will add insights on how to better approach this in the future.

• Preventing evaluation does not prevent the pattern matcher from looking at attributes of heads.
• Using Block can prevent the special properties of heads from confusing the issue.
• When using multiple BlankSequence, one must consider the greediness of the pattern matcher.

Answer 2

Maybe someone can come up with a good explanation why this is a bug, but I believe it is more a feature. It is not specifically bound to Times, but this works for every function with the Orderless attribute.

That being said, we can check whether or not the pattern matching and replacing leaks evaluation, because this would be the only reason for a reordering of the arguments: The function gets evaluated in the process of replacement. Therefore, let's start simple

test[___] := Throw["Error"];
SetAttributes[test, Attributes[Times]]

Hold[test[a, b, f[], c]] /. 
  HoldPattern[test[x__, f[], y__]] :> {{x}, f[], {y}}
(* Hold[{{a}, f[], {b, c}}] *)

Still reorders the arguments and it seems nothing gets evaluated. It almost seems this is intentional. Maybe it has proven to be required for some practical reasons.

Finally, in your current example, you pattern gets pretty much fixed with the appearance of f[]. Therefore, a shorter solution to the problem is to skip the Times head completely

HoldForm[Times[a,b,f[],c]]/._[x__,f[],y__]:>{{x},f[],{y}}
(* {{a,b},f[],{c}} *)

or if you insist, then it is enough to hide it a bit

HoldForm[Times[a,b,f[],c]]/.(_:Times)[x__,f[],y__]:>{{x},f[],{y}}
(* {{a,b},f[],{c}} *)