# 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.

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.