Flat and Orderless Functions

Although the Wolfram Language matches patterns in a purely structural fashion, its notion of structural equivalence is quite sophisticated. In particular, it takes account of properties such as commutativity and associativity in functions like (RefLink[Plus, paclet:ref/Plus]) and (RefLink[Times, paclet:ref/Times]).

This means, for example, that the Wolfram Language considers the expressions x+y and y+x equivalent for the purposes of pattern matching. As a result, a pattern like g[x_+y_,x_] can match not only g[a+b,a], but also g[a+b,b].

This expression has exactly the same form as the pattern:

g[a+b,a]/.g[x_+y_,x_]->p[x,y]

In this case, the expression has to be put in the form g[b+a,b] in order to have the same structure as the pattern:

g[a+b,b]/.g[x_+y_,x_]->p[x,y]

Whenever the Wolfram Language encounters an orderless or commutative function such as (RefLink[Plus, paclet:ref/Plus]) or (RefLink[Times, paclet:ref/Times]) in a pattern, it effectively tests all the possible orders of arguments to try and find a match. Sometimes, there may be several orderings that lead to matches. In such cases, the Wolfram Language just uses the first ordering it finds. For example, h[x_+y_,x_+z_] could match h[a+b,a+b] with x→a, y→b, z→b or with x→b, y→a, z→a. The Wolfram Language tries the case x→a, y→b, z→b first, and so uses this match.

This can match either with x→a or with x→b. The Wolfram Language tries x→a first, and so uses this match:

h[a+b,a+b]/.h[x_+y_,x_+z_]->p[x,y,z]

(RefLink[ReplaceList, paclet:ref/ReplaceList]) shows both possible matches:

ReplaceList[h[a+b,a+b],h[x_+y_,x_+z_]->p[x,y,z]]

As discussed in "Attributes", the Wolfram Language allows you to assign certain attributes to functions, which specify how those functions should be treated in evaluation and pattern matching. Functions can for example be assigned the attribute (RefLink[Orderless, paclet:ref/Orderless]), which specifies that they should be treated as commutative or symmetric, and allows their arguments to be rearranged in trying to match patterns.

Some attributes that can be assigned to functions.

(RefLink[Plus, paclet:ref/Plus]) has attributes (RefLink[Orderless, paclet:ref/Orderless]) and (RefLink[Flat, paclet:ref/Flat]), as well as others:

Attributes[Plus]

This defines q to be an orderless or commutative function:

SetAttributes[q,Orderless]

The arguments of q are automatically sorted into order:

q[b,a,c]

The Wolfram Language rearranges the arguments of q functions to find a match:

f[q[a,b],q[b,c]]/.f[q[x_,y_],q[x_,z_]]->p[x,y,z]

In addition to being orderless, functions like (RefLink[Plus, paclet:ref/Plus]) and (RefLink[Times, paclet:ref/Times]) also have the property of being flat or associative. This means that you can effectively "parenthesize" their arguments in any way, so that, for example, x+(y+z) is equivalent to x+y+z, and so on.

The Wolfram Language takes account of flatness in matching patterns. As a result, a pattern like g[x_+y_] can match g[a+b+c], with x→a and y→(b+c).

The argument of g is written as a+(b+c) so as to match the pattern:

g[a+b+c]/.g[x_+y_]->p[x,y]

If there are no other constraints, the Wolfram Language will match x_ to the first element of the sum:

g[a+b+c+d]/.g[x_+y_]->p[x,y]

This shows all the possible matches:

ReplaceList[g[a+b+c],g[x_+y_]->p[x,y]]

Here x_ is forced to match b+d:

g[a+b+c+d,b+d]/.g[x_+y_,x_]->p[x,y]

The Wolfram Language can usually apply a transformation rule to a function only if the pattern in the rule covers all the arguments in the function. However, if you have a flat function, it is sometimes possible to apply transformation rules even though not all the arguments are covered.

This rule applies even though it does not cover all the terms in the sum:

a+b+c/.a+c->p

This combines two of the terms in the sum:

u[a]+u[b]+v[c]+v[d]/.u[x_]+u[y_]->u[x+y]

Functions like (RefLink[Plus, paclet:ref/Plus]) and (RefLink[Times, paclet:ref/Times]) are both flat and orderless. There are, however, some functions, such as (RefLink[Dot, paclet:ref/Dot]), which are flat, but not orderless.

Both x_ and y_ can match any sequence of terms in the dot product:

a.b.c.d.a.b/.x_.y_.x_->p[x,y]

This assigns the attribute (RefLink[Flat, paclet:ref/Flat]) to the function r:

SetAttributes[r,Flat]

The Wolfram Language writes the expression in the form r[r[a,b],r[a,b]] to match the pattern:

r[a,b,a,b]/.r[x_,x_]->rp[x]

The Wolfram Language writes this expression in the form r[a,r[r[b],r[b]],c] to match the pattern:

r[a,b,b,c]/.r[x_,x_]->rp[x]

In an ordinary function that is not flat, a pattern such as x_ matches an individual argument of the function. But in a function f[a,b,c,…] that is flat, x_ can match objects such as f[b,c] which effectively correspond to a sequence of arguments. However, in the case where x_ matches a single argument in a flat function, the question comes up as to whether the object it matches is really just the argument a itself, or f[a]. The Wolfram Language chooses the former possibility if the function carries the attribute (RefLink[OneIdentity, paclet:ref/OneIdentity]), otherwise it will first attempt to use the latter but fall back on the former.

This adds the attribute (RefLink[OneIdentity, paclet:ref/OneIdentity]) to the function r:

SetAttributes[r,OneIdentity]

Now x_ matches individual arguments, without r wrapped around them:

r[a,b,b,c]/.r[x_,x_]->rp[x]

The functions (RefLink[Plus, paclet:ref/Plus]), (RefLink[Times, paclet:ref/Times]), and (RefLink[Dot, paclet:ref/Dot]) all have the attribute (RefLink[OneIdentity, paclet:ref/OneIdentity]), reflecting the fact that (RefLink[Plus, paclet:ref/Plus])[x] is equivalent to x, and so on. However, in representing mathematical objects, it is often convenient to deal with flat functions that do not have the attribute (RefLink[OneIdentity, paclet:ref/OneIdentity]).