# Grouping expressions by associative equivalence for a single operation

I would like to group expressions under associative equivalence, but only for a specific operation used in the expression (not for other operations).

Say we have two binary operations A and B applicable to positive integers and producing positive integer outcomes (for instance + and x on the positive integers). Expressions of the following type can be formed

A(3,1), B(7,9), A(B(1,2),3), B(A(2,1),A(B(1,3),5)), ...

The aim is to group such expressions according to equivalence under associative recombination of one of the operations. Say for operation A.

For instance (replacing arbitrary positive integers with an atom x for clarity):

A(B(x,x), A(x, A(x,x))) should be equivalent to A(A(A(B(x,x),x),x),x)

But no changes should be made to expressions using B in which associative recombinations could potentially be made.

For instance:

B(B(A(x,x),x), B(x, B(x,x))) should not be equivalent to B(B(B(B(A(x,x),x),x),x),x)

Are there commands in Mathematica that test expressions for associative equivalence for a particular, i.e. fixed choice of operation?

I don't wish to make the expressions literally equivalent to one another and collapse them to a single representative. I just wish to group them into say lists of equivalent expressions.

ETA I found a reference to Flatten" and am considering to use it as in:

Flatten[A[B[u, v], A[x, y]], Infinity, A]

I will leave the post up, and wonder whether I could just check for associative equivalence this way?

For instance via:

Flatten[A(B(x,x), A(x, A(x,x))), Infinity, A] == Flatten[A(A(A(B(x,x),x),x),x), Infinity, A]

• does SetAttributes[A, {Flat, Orderless}] help at all? – kglr Jun 21 at 13:29
• I think that would make them equivalent, rather than group them by equivalence. I found a command Flatten". Not sure yet it will do the trick but I adjusted my post. Have to head off to work soon, but will revisit later today. – Mike Jun 21 at 13:37
• so A is not associative but in grouping the list of expressions you want to process each expression as if A is associative? – kglr Jun 21 at 13:58
• Yes, I want to keep A not associative, but group it as if it were. – Mike Jun 21 at 14:50
• Using Flatten[A (B (x, x), A (x, A (x, x))), Infinity, A] produces an error: Syntax: "(" cannot be followed by "B(x,x),A(x,A(x,x)))". Not sure what the problem is – Mike Jun 21 at 14:53

Flatten is a nice approach.

You can also do:

ClearAll[asIfAWereAssociative]
asIfAWereAssociative = Block[{a}, SetAttributes[a, Flat]; # /. A -> a] &;

expressions = {A[B[x, x], A[x, A[x, x]]], A[A[A[B[x, x], x], x], x]};
Equal @@ (asIfAWereAssociative /@ expressions)


True

GatherBy[expressions, asIfAWereAssociative]


{{A[B[x, x], A[x, A[x, x]]], A[A[A[B[x, x], x], x], x]}}

DeleteDuplicatesBy[expressions, asIfAWereAssociative]


{A[B[x, x], A[x, A[x, x]]]}

• Thanks! Beautiful solution. I sort of gather what Block is meant to achieve here: a local interpretation of A as being associative. GatherBy then collects the copies that are the same under this local identification. There is so much to know about Mathematica and I struggle at times to find the right operations.I have the book, but wonder if there are other introductions available for the language that you might recommend? – Mike Jun 21 at 15:28
• Specifically introductions focused on expression manipulation. – Mike Jun 21 at 15:33
• Thank you @Mike for the accept (I would prefer your Flatten approach). I think you might be aware of Where can I find examples of good Mathematica programming practice? . I keep Leonid Shifrin, Stan Wagon and Sal Mangano's books handy. – kglr Jun 21 at 15:39
• Thanks for the resources! I think that Shifrin is exactly what I need. Nice travel literature for upcoming trip :) I want to focus on the language first. I adapted your GatherBy approach to: GatherBy[expressions, Flatten[#, Infinity, A] &] which works as you suggest. – Mike Jun 21 at 15:50
• Is it possible to filter out atoms? Flatten gives a warning on those. For instance Flatten[3, Infinity, A] gives: Flatten::normal: Nonatomic expression expected at position 1 in Flatten[3,[Infinity],A]. I want to add a test for AtomQ[#]. Something like: GatherBy[expressions, Flatten[#, Infinity, A] /; !AtomQ[#] &] This produces the same error though. ETA: never mind, got it: Flatten[# /; ! AtomQ[#], Infinity, A] &] – Mike Jun 21 at 16:40

Ok, the answer seems to be the following, expressions need to be compared using flatten, which detects associative equivalence for A based on supplying A as third argument of flatten and specifying Infinity to check at all levels (of bracket nesting)

Flatten[A[B[x, x], A[x, A[x, x]]], Infinity, A] == Flatten[A[A[A[B[x, x], x], x], x], Infinity, A]

ETA: And based on kglr's suggestion:

GatherBy[expressions, Flatten[#, Infinity, A] &]

Slightly simpler, but basically equivalent to the accepted answer is:

SetAttributes[a, Flat];
GatherBy[expressions, ReplaceAll[A->a]]


{{A[B[x, x], A[x, A[x, x]]], A[A[A[B[x, x], x], x], x]}}