# Recursion depth exceeded in pattern matching with attribute Flat

I am defining a linear associative multiplication operation Mult[]:

ClearAll[Mult]
SetAttributes[Mult, {Flat, OneIdentity}];
Mult[A___, a_, B___] := a Mult[A, B] /; NumberQ[a]


Then I try to evaluate a simple expression, which (I believe) does not match the rule written above:

Mult[X, Y]


I got the error Recursion depth of 1024 exceeded. It is definitely related to the attribute Flat, but I do not see how. What am I doing wrong?

I find Flat hard to work with. Despite seeing it in use numerous times I'm never quite sure what it will do until I try it, so maybe I'm not the person to answer your question. Nevertheless I shall try.

Consider this related, reduced example:

Attributes[foo] = {Flat, OneIdentity};
foo[a_] := "inert" /; Print @ HoldForm[a]

foo[X, Y];

foo[X,Y]

X

Y


Critically the entire expression foo[X, Y] is substituted for the pattern a_ in one of the match attempts. This leads to infinite recursion.

One way to get around this is to prevent evaluation of that expression, which is what I used HoldForm for above. Applied to your original function:

ClearAll[Mult]
Attributes[Mult] = {Flat, OneIdentity};
Mult[A___, a_, B___] := a Mult[A, B] /; NumberQ[Unevaluated @ a]

Mult[X, Y]

Mult[3, x, 7, y, z]

Mult[X, Y]

21 Mult[x, y, z]


This is basically a duplicate of question (5067). You can use my answer to that question to resolve your issue:

ClearAll[Mult]
SetAttributes[Mult, {Flat, OneIdentity}];
Verbatim[Mult][A___, a_, B___] := a Mult[A,B] /; NumberQ[a]


Then:

Mult[X, Y]
Mult[3, X, 7, Y, Z]


Mult[X, Y]

21 Mult[X, Y, Z]

No recursion errors.

Comparison

Using Verbatim should be much quicker than the accepted answer, because those patterns where a gets matched with a Mult object should never happen. The accepted answer (using Mult2):

ClearAll[Mult2]
Attributes[Mult2] = {Flat, OneIdentity};
Mult2[A___, a_, B___] := a Mult2[A,B] /; NumberQ[Unevaluated@a]


And a comparison:

SeedRandom[1]
r = RandomChoice[Join[Alphabet[], Range[10]], 30];

r1 = Mult @@ r; //AbsoluteTiming
r2 = Mult2 @@ r; //AbsoluteTiming

ReplaceAll[Mult->List] @ r1 === ReplaceAll[Mult2->List] @ r2


{0.000206, Null}

{0.025536, Null}

True

• I'm probably missing an important point here but isn't this like leaving out Flat to begin with? Doesn't an actual solution need to preserve that pattern-matching behavior? (I am assuming that this is a toy example and not the actual, complete problem.) – Mr.Wizard Sep 24 '18 at 14:53
• @Mr.Wizard Flat has two main characteristics, pattern matching and associativity. The pattern matching is interfering with the DownValues, so using Verbatim disables it. The associativity still works, e.g., Mult[a, Mult[b, c]] still evaluates to Mult[a, b, c]. – Carl Woll Sep 24 '18 at 14:58
• I can't think of an example where that pattern behavior is needed within the definition itself but I suspect one exists. Nevertheless for the case at hand I see the superiority of your method. Do you think this question should be closed as a duplicate of 5067? – Mr.Wizard Sep 24 '18 at 15:04
• @Mr.Wizard Perhaps a related comment would be sufficient? I think it's slightly different. – Carl Woll Sep 24 '18 at 15:11
• Okay. The content of your post already includes 5067 in the Linked bar to the right. – Mr.Wizard Sep 24 '18 at 15:14