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 Plus and 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].
Whenever the Wolfram Language 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, 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.
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 Orderless, which specifies that they should be treated as commutative or symmetric, and allows their arguments to be rearranged in trying to match patterns.
|Orderless||commutative function: f[b,c,a], etc., are equivalent to f[a,b,c]|
|Flat||associative function: f[f[a],b], etc., are equivalent to f[a,b]|
|OneIdentity||f[f[a]], etc., are equivalent to a|
|Attributes[f]||give the attributes assigned to f|
|SetAttributes[f,attr]||add attr to the attributes of f|
|ClearAttributes[f,attr]||remove attr from the attributes of f|
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, x+(y+z) is equivalent to x+y+z, and so on.
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.
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 OneIdentity, otherwise it will first attempt to use the latter but fall back on the former.
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.