Create pattern to “redo” Nest for symbolic purposes, e.g. for commutators

Question

I am symbolically working with matrix commutators (comm) and face the following issue: There are nested commutators in my final results, defined as

NestedComm[mat1_, mat2_, n_] /; n > 1 := comm[NestedComm[mat1, mat2, n - 1], mat2];
NestedComm[mat1_, mat2_, 1] := comm[mat1, mat2];
NestedComm[mat1_, mat2_, 0] := mat1;

which due to the nature of the algorithm appear for instance as comm[comm[comm[a,b],b],b] in my final expressions. Note that the level of nesting n can in principle be anything from one to infinity. In order to make the results more readable, I am looking for a pattern or something else that would transform comm[comm[comm[a, b], b], b] to nestedComm[a,b,3] (the lowercase letter would be intended to avoid evaluation of the actual definition and to avoid the need of messing around with Hold and the like). The pattern should of course only apply if it is really a nested commutator according to the definition of NestedComm - there are also terms like comm[comm[comm[a,b],c],b] which should stay untouched by the transformation.

Is it somehow possible to automatically recognize this type of Nested functions and the corresponding level of nesting in order to replace them with a shorthand notation?

Update: It has not been clear from the question, that I do not want the nested comm[]objects to simplify automatically everywhere. Actually, my algorithm relies on them not being transformed to nestedComm[] throughout many steps of computation. But since the expressions may become quite involved and long, I would like to use a replacement rule/function/... on the final result, so that the nested objects are only simplified where I want them to be.

Answer 1

You might use transformation rules to transform nested commutators to nestedComm :

nestedCommRules = {
    comm[comm[a_, b_], b_] :> nestedComm[a, b, 2], 
    nestedComm[comm[a_, b_], b_, n_] :> nestedComm[a, b, n + 1]
}

(It's possible that you may want to include comm[nestedComm[a_, b_, n_], b_] :> nestedComm[a, b, n + 1] as well, but you don't need it for your example above.)

Then you can do

comm[comm[comm[a, b], b], b] //. nestedCommRules
(* nestedComm[a, b, 3] *)

comm[comm[comm[a, b], c], b] //. nestedCommRules
(* comm[comm[comm[a, b], c], b] *)

You mentioned pattern matching, so I'm not sure this answers your question fully. Hopefully it's a start.

Note that you can use NestedComm instead of nestedComm if you implemented the original definitions of NestedComm using transformation rules rather than SetDelayed, but this is of course your choice.

Answer 2

Speed

We can make jjc385's operation far more efficient by replacing from the inside out, rather than repeatedly scanning the entire expression from the top down using //., as explained in How to remove redundant {} from a nested list of lists? and elsewhere.

Updated to scan only down to levelspec -3 for slightly improved efficiency.

Let's compare performance on a deeply nested expression.

nestedCommRules = {comm[comm[a_, b_], b_] :> nestedComm[a, b, 2], 
  nestedComm[comm[a_, b_], b_, n_] :> nestedComm[a, b, n + 1]};

inOutRules = {comm[comm[a_, b_], b_] :> nestedComm[a, b, 2], 
   comm[nestedComm[a_, b_, n_], b_] :> nestedComm[a, b, n + 1]};

deep = Nest[comm[#, b] &, a, 5000];

deep //. nestedCommRules            // RepeatedTiming
Replace[deep, inOutRules, {0, -3}]  // RepeatedTiming

{0.234, nestedComm[a, b, 5000]}

{0.00388, nestedComm[a, b, 5000]}

Simplicity

I would encourage you to consider a different form that makes replacement simpler: comm[a, b, 3] to represent comm[comm[comm[a, b], b], b].

deep = Nest[comm[#, b] &, a, 5000];


rule = comm[comm[a_, b_, n_: 1], b_] :> comm[a, b, n + 1];

Replace[deep, rule, {0, -3}] // RepeatedTiming

{0.00455, comm[a, b, 5000]}

If that format won't work for you then perhaps:

rule =
  comm[(nestedComm | comm)[a_, b_, n_: 1], b_] :> nestedComm[a, b, n + 1];

Replace[deep, rule, {0, -3}] // RepeatedTiming

{0.00473, nestedComm[a, b, 5000]}

Answer 3

An alternative is to use TagSetDelayed[] to set rules on how your comm[] and nestedComm[] objects should act. For instance:

comm /: comm[comm[x_, y_], y_] := nestedComm[x, y, 2];

comm /: comm[nestedComm[x_, y_, k_Integer?NonNegative], y_] := nestedComm[x, y, k + 1]

After evaluating those:

comm[comm[comm[a, b], b], b]
   nestedComm[a, b, 3]

comm[comm[comm[a, b], c], b]
   comm[comm[comm[a, b], c], b]