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).
{a, b, c, d, a, b} /. {___, x_, y___, x_, ___} -> p[{x}, {y}]
$\endgroup$a . b . c . d . a . b /. a . b -> x
givesx.c.d.a.b
but this could be due to the Flat nature of "."? $\endgroup$ReplaceRepeated[a.b.c.d.a.b, a.b -> x]
:) $\endgroup$