Why is a longer pattern matched rather than a short pattern?

Question

I was reading the Mathematica V5 Book and am a bit perplexed on the behavior of a particular pattern matching example where it seems to be choosing a longer pattern rather than a shorter pattern.

The example from page 272:

In[15]:= a.b.c.d.a.b /. x_ . y_ . x_ -> p[x,y]

Out[15]= p[a.b, c.d]

I initial thought that the shorter pattern "a.b.c.d.a" would be matched to give something such as (not that it is guaranteed to produce anything syntactically meaningful):

In[#]:= a.b.c.d.a.b /. x_ . y_ . x_ -> p[x,y]

Out[#+1]= p[a,b.c.d].b

Since,

In[#]:= a.b.c.d.a /. x_ . y_ . x_ -> p[x,y]

Out[#+1]= p[a,b.c.d]

But, even checking the all possible matched patterns with ReplaceList only gives the pattern from the example:

In[#]:= ReplaceList[a . b . c . d . a . b , x_ . y_ . x_ -> p[x, y]]

Out[#+1]:= {p[a.b, c.d]}

However, the actual example behavior shown on page 272 seems to contradict the explanation on page 274 where it states:

"When you use multiple blanks, there are often several matches that are possible for a particular expression. In general, Mathematica tries first those matches that assign the shortest sequences of arguments to the first multiple blanks that appear in pattern."

I am either lost in how the pattern is matching 1) something that is Flat or 2) that "multiple blanks" means multiple "multiple blanks" and not multiple "blanks" so the above explanation somehow does not apply?

Any thoughts on what I am missing?

Answer 1

The results we see are due to a subtle interaction between the Flat attribute of Dot and the outermost-in, left-to-right scanning strategy employed by the pattern matcher.

The expression

a . b . c . d . a . b /. x_ . y_ . x_ :> p[x,y]

could legitimately return three different solutions depending upon how we decide to group the . (Dot) operators, namely:

(a.b).(c.d).(a.b)   ->   p[a.b, c.d]
(a.(b.c.d).a).b     ->   p[a, b.c.d] . b
a.(b.(c.d.a).b)     ->   a . p[b, c.d.a]

The subparts of these three possibilities overlap. As a result, ReplaceAll can only return one of these possibilities because it will never revisit a subexpression that has been successfully matched. The first match that it finds will be returned, which happens to be the first result on this list.

We might think that ReplaceList should find all three of these results. But it will not because, unlike ReplaceAll, ReplaceList will only apply a transformation to the whole expression -- not subparts. This disqualifies the second and third results on account of the trailing . b and leading a . respectively.

It is no coincidence that the result chosen seemingly arbitrarily by ReplaceAll is the same as the sole possibility returned by ReplaceList. ReplaceAll works from the outermost level inward, only descending into a sublevel once it has exhausted possibilities from the level above. At each level, processing proceeds from left-to-right in accordance with the general principle cited in the Mathematica book ("In general [...] shortest sequence[...] to the first"). Note, however, that in nested structures the left-to-right principle is subsidiary to the outermost-inward principle.

This brings us to the complication introduced by the Flat attribute of Dot. To explore this without the distraction of the . short form for Dot, we will define our own flat operator that exhibits the same behaviour:

SetAttributes[f, Flat]

f[a, b, c, d, a, b] /. f[x_, y_, x_] :> p[x, y]
(* p[f[a, b], f[c, d]] *)

The critical thing to note about Flat is that it forces the pattern-matcher to "unflatten" expressions for matching purposes as necessary. Consider:

f[a, b] /. f[a] -> 1
(* f[1, b] *)

The apparently flat expression f[a, b] had to be treated as if it were written in the non-flat form f[f[a], b] in order to match correctly. Such "unflattening" can generate many possible candidate patterns. For example, consider that all of the following expressions are equivalent for matching purposes:

f[a, b]
f[f[a], b]
f[a, f[b]]
f[f[a, b]]
f[f[f[a], b]]
f[f[a, f[b]]]
f[f[f[a], f[b]]]
... and so on ...

The case at hand exhibits this property, where the pattern matcher must generate and scan a large list of possibilities. We can trick Replaceall into revealing all matches by adding an always-false condition that, as a side-effect, captures each valid match using Sow/Reap:

f[a, b, c, d, a, b] /. f[x_, y_, x_] :> 0 /; (Sow[p[x, y]]; False) //
  Reap // #[[2, 1]]& // Column

(*
p[f[a,b],f[c,d]]
p[f[a],f[b,c,d]]
p[f[b],f[c,d,a]]
*)

This will only reveal the matches, not the fully replaced forms. Alas, Mathematica presently lacks a multi-level ReplaceList operator.

It is hard to spot the scan pattern in this short list. Let's loosen the pattern a little and change the condition to print every three-element sequence scanned, marking matches with ***:

f[a, b, c, d, a, b] /. f[x_, y_, z_] :> 0 /;
  ( {x, y, z} // Print @ Row @ {#, # /. {{a_, b_, a_} -> " ***", _ -> Nothing}}&
  ; False
  )

(*
{f[a],f[b],f[c,d,a,b]}
{f[a],f[b,c],f[d,a,b]}
{f[a],f[b,c,d],f[a,b]}
{f[a],f[b,c,d,a],f[b]}
{f[a,b],f[c],f[d,a,b]}
{f[a,b],f[c,d],f[a,b]} ***
{f[a,b],f[c,d,a],f[b]}
{f[a,b,c],f[d],f[a,b]}
{f[a,b,c],f[d,a],f[b]}
{f[a,b,c,d],f[a],f[b]}
{f[a],f[b],f[c,d,a]}
{f[a],f[b,c],f[d,a]}
{f[a],f[b,c,d],f[a]} ***
{f[a,b],f[c],f[d,a]}
{f[a,b],f[c,d],f[a]}
{f[a,b,c],f[d],f[a]}
{f[b],f[c],f[d,a,b]}
{f[b],f[c,d],f[a,b]}
{f[b],f[c,d,a],f[b]} ***
{f[b,c],f[d],f[a,b]}
{f[b,c],f[d,a],f[b]}
{f[b,c,d],f[a],f[b]}
{f[a],f[b],f[c,d]}
{f[a],f[b,c],f[d]}
{f[a,b],f[c],f[d]}
{f[b],f[c],f[d,a]}
{f[b],f[c,d],f[a]}
{f[b,c],f[d],f[a]}
{f[c],f[d],f[a,b]}
{f[c],f[d,a],f[b]}
{f[c,d],f[a],f[b]}
{f[a],f[b],f[c]}
{f[b],f[c],f[d]}
{f[c],f[d],f[a]}
{f[d],f[a],f[b]}

f[a,b,c,d,a,b]
*)

This output shows the general unflattening strategy. Careful inspection shows that the outer levels are considered before their inner parts. We can see also the left-to-right processing within a given level and, as stated in the documentation, the left-most pattern blanks are filled with progressively longer substitutions (but not so for the blanks further right).

Answer 2

Look at the FullForm of the expression

FullForm[a.b.c.d.a.b]

Dot[a,b,c,d,a,b]

and the replacement pattern

FullForm[x_ . y_ . x_]

Dot[Pattern[x,Blank[]], Pattern[y,Blank[], Pattern[x,Blank[]]]

Clearly both the expression and the pattern are enclosed by Dot[...].

So what we need is for:

Dot[a,b,c,d,a,b] and Dot[x_, y_, x_] to match.

The only possible way to match the pattern to the expressions is to assign x = a,b and y=c,d.

The combination x=a, y=b,c,d doesn't match because there is a floating b at the end. To see that this is so, let's insert these values into the expression:

Dot[a,b,c,d,a,b] becomes Dot[x, y, x, b].

Clearly the latter doesn't match Dot[x, y, x].

So to summarize it is not the case of longer or shorter pattern matching, rather it is the case of the only pattern that matches.