Flat and Orderless Functions
Although Mathematica 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 Plus and Times.
This means, for example, that Mathematica considers the expressions 
and 
equivalent for the purposes of pattern matching. As a result, a pattern like 
can match not only 
, but also 
.
This expression has exactly the same form as the pattern.
| Out[1]= |  |
In this case, the expression has to be put in the form
in order to have the same structure as the pattern.
| Out[2]= |  |
Whenever Mathematica encounters an orderless or commutative function such as Plus or 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, Mathematica just uses the first ordering it finds. For example, 
could match 
with 
, 
, 
or with 
, 
, 
. Mathematica tries the case 
, 
, 
first, and so uses this match.
| Out[3]= |  |
| Out[4]= |  |
As discussed in "Attributes", Mathematica 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 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.
| Out[5]= |  |
This defines
to be an orderless or commutative function.
The arguments of
are automatically sorted into order.
| Out[7]= |  |
Mathematica rearranges the arguments of
functions to find a match.
| Out[8]= |  |
In addition to being orderless, functions like Plus and 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, 
is equivalent to 
, and so on.
Mathematica takes account of flatness in matching patterns. As a result, a pattern like 
can match 
, with 
and 
.
The argument of
is written as
so as to match the pattern.
| Out[9]= |  |
If there are no other constraints,
Mathematica will match
to the first element of the sum.
| Out[10]= |  |
This shows all the possible matches.
| Out[11]= |  |
Here
is forced to match
.
| Out[12]= |  |
Mathematica 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.
| Out[13]= |  |
This combines two of the terms in the sum.
| Out[14]= |  |
Functions like Plus and Times are both flat and orderless. There are, however, some functions, such as Dot, which are flat, but not orderless.
Both
and
can match any sequence of terms in the dot product.
| Out[15]= |  |
This assigns the attribute
Flat to the function
.
Mathematica writes the expression in the form
to match the pattern.
| Out[17]= |  |
Mathematica writes this expression in the form
to match the pattern.
| Out[18]= |  |
In an ordinary function that is not flat, a pattern such as 
matches an individual argument of the function. But in a function 
that is flat, 
can match objects such as 
which effectively correspond to a sequence of arguments. However, in the case where 
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 
. Mathematica chooses the first of these cases if the function carries the attribute OneIdentity, and chooses the second case otherwise.
Now
matches individual arguments, without
wrapped around them.
| Out[20]= |  |
The functions Plus, Times, and Dot all have the attribute OneIdentity, reflecting the fact that 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 OneIdentity.
, etc., are equivalent to 
, etc., are equivalent to 
, etc., are equivalent to a
