8
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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]
$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Mr.Wizard Sep 24 '18 at 14:53
  • $\begingroup$ @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]. $\endgroup$ – Carl Woll Sep 24 '18 at 14:58
  • $\begingroup$ 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? $\endgroup$ – Mr.Wizard Sep 24 '18 at 15:04
  • $\begingroup$ @Mr.Wizard Perhaps a related comment would be sufficient? I think it's slightly different. $\endgroup$ – Carl Woll Sep 24 '18 at 15:11
  • $\begingroup$ Okay. The content of your post already includes 5067 in the Linked bar to the right. $\endgroup$ – Mr.Wizard Sep 24 '18 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.