Chapter IV.  Pattern Matching in Symbolic Programming

11. Pattern Matching and Conditional Evaluation

Last revision:  February 18 1998

In this section we introduce several ways in which Mathematica's pattern matching capabilities permit better coding of functions.  Pattern-matching is a feature found primarily in symbolic programming languages such as Mathematica, but not in procedural or object-oriented languages such as C, C++, or Pascal.  The most basic sort of pattern matching we consider is data type checking for parameters, followed by general boolean parameter tests (and their variants, conditions) and then more structured patterns, with which we can assign parameter names to parts of a parameter.  During this section we also treat ways in which code can be written to be readable and user-friendly, informing the user of invalid parameters.

Mathematica operations/structures introduced: 
     parameter_?testQ
     Print[]
     Trace[]
     ??name
     ::usage=
     Positive[]
     /;
     \;

Data Type Checking and Other Boolean Parameter Tests

Data Type Checking

Most functions require, or at least "expect", certain data types for the values they receive as parameters.  That is, a function written to accept a list as its parameter may not work properly if it is invoked with a string as its parameter instead.  For instance, suppose we are developing a function to produce Pascal's Triangle, the first few rows of which are the following.

One operation we might require in the production of the triangle is the appending and prepending of "1"'s; each row can be derived from the row above by taking sums of successive entries and then prepending and appending a "1".  Such a function might be defined as follows:

Clear[addOnes]
addOnes[list_] := Append[Prepend[list,1],1]

Our function "addOnes[]" works well if the actual parameter substituted for "list" in the function is, in fact, a list; otherwise, disastrous results occur.

addOnes["disaster"]

A good programming principle is that functions should "catch" these errors before they can happen;  functions should determine first whether the input values of the parameters are valid, and only then proceed to use the values.  If the input values are not suitable for the function, a message should be returned to the user, explaining that fact.  We can implement this principle using data type checking, where we specify that a definition of a function should be executed only when certain conditions on the data types of input values of the parameters hold true.  

To have Mathematica automatically check a type of a parameter, insert the name of the data type after the underscore in the function definition.  For example, instead of defining "f[x_]:=x^2", we can insist that "f" have the definition "x^2" for integers only by executing "f[x_Integer] := x^2". Similarly, to insist that the parameter "list" above be of type List, we use "list_List" instead of "list_" in the function definition.

Clear[addOnes]
addOnes[list_List] := Append[Prepend[list,1],1]

addOnes[{4,6,4}]

addOnes["disaster"]

Notice that when Mathematica determines that the data type does not match the required type, it simply returns the executed expression back, unevaluated.  We can instruct Mathematica to allow several different data types by writing separate definitions for the function with each of the specified data types.  For example, we define below several different definitions for "addOnes[]", depending on the data type of the input:

Clear[addOnes]
addOnes[list_List] := Append[Prepend[list,1],1]
addOnes[s_String] := StringJoin["1",s,"1"]
addOnes[i_Integer] := 1 + i + 1

addOnes["dog"]
addOnes[{4,6,4}]
addOnes[50]

Boolean Parameter Tests; Error Messages (Print)

We may, however, want to check our data more generally.  For instance, might we want to define a function which works on all numbers (including, say, Integers, Rationals, and Reals), but not on strings?  Might we want to define a function which only works on positive integers?  Mathematica provides a way for us to apply any boolean test to each parameter, instructing Mathematica that the given definition of the function should be used only if each of the boolean tests returns a True.  The syntax is to place a boolean function's name, with a question mark prepended, after the underscore of the corresponding parameter.

Clear[addOnes]
addOnes[list_List] := Append[Prepend[list,1],1]
addOnes[i_?NumberQ] := 1 + i + 1
addOnes[s_?((StringQ[#]&&StringLength[#]>3)&)] :=
			StringJoin[s," and so on"]

addOnes[{4,6,4}]
addOnes["dog"]
addOnes["Dogs and cats"]
addOnes[45.4]
addOnes[23]

Recall that Mathematica has a whole array of "Q" functions which perform boolean tests on their parameters; we have used "NumberQ[]" above.  Also, note the use of an anonymous boolean function to check whether or not the parameter is a String and if its length is greater than 3. Remember to put parentheses around an entire anonymous function definition, including the final ampersand ("&"), when using it as a parameter check.

Using boolean tests, we can alert the user to the fact that the parameter values are in error.  To do so, write an extra definition which tests whether the data is invalid and uses a "Print[]" statement in the definition to print an error message.  For example, to alert the user that only lists are appropriate for "addOnes[]", we might expand our definition as follows:

Clear[addOnes]
addOnes[list_List] := Append[Prepend[list,1],1]
addOnes[list_?(!ListQ[#]&)] := 
			Print["Parameter not a list!"]

Note that the function "Print[]" displays its parameter but returns nothing; in this way we prevent our function from passing some string back to an expression that used it.

addOnes[{4,6,4}]
addOnes[4]

Using Specific and General Definitions Together

Specific First, General After

We saw above that Mathematica can store several definitions for the same function.  In fact, every time we execute a definition for a function, Mathematica adds this definition to its list, unless we have used "Clear[]" to erase the previous definitions.  How, then, does Mathematica decide which definition to use, if several definitions are appropriate?  The answer, roughly, is that Mathematica attempts to decide which of the valid definitions places the least general, or most specific, constraints on its parameters, and uses that definition.  Mathematica will not always be able to determine which definition is "most specific", but in most of the cases we will consider, its internal rules for deciding specificity will work correctly.  Let us consider how we can use this versatility of Mathematica to our advantage.

Suppose we must implement a peculiar function, one which squares its input unless that input is a 3, in which case it returns an 8.  Using our boolean tests above, we would likely write the following code.

Clear[f];
f[x_?((#==3)&)] = 8;
f[x_?((#!=3)&)] = x^2;

Table[{i,f[i]},{i,1,5}]

We can accomplish the same operations by instructing Mathematica that the general definition is "f[x_]:=x^2", while a more specific rule is "f[3]=8".  Note that we do not append an underscore to the 3:  if we do not wish to allow any value for the parameter except for the value specified, we do not append an underscore.

Clear[f];
f[3]=8;
f[x_] := x^2;

Table[{i,f[i]},{i,1,5}]

Let's look at what definitions Mathematica has stored for our function "f[]":

?f

Now let us recode the function "addOnes[]" to accept only lists, returning an error message otherwise.  We can do so much more cleanly than we could before:

Clear[addOnes]
addOnes[list_List] := Append[Prepend[list,1],1]
addOnes[list_] := 
	Print["Parameter \"",list,"\" is not a list!"]

addOnes[{2,3}]

addOnes[1]

(Note the interesting use of the "Print[]" function: we are instructing it to print out the parameter "list" with two strings on either side.  The first string ends with a quotation mark inside, indicated by a special code---a slash before a quotation mark---and the second string begins with the same quotation mark.)

Application:  Using Multiple Definitions for Recursion (Trace)

Multiple definitions are often used when implementing the method of recursion, where a function, during execution, executes itself again, with other parameters. Recall our example of the recursive solution to implementing a factorial function:

Clear[fac]
fac[1] = 1 ;
fac[n_] := n fac[n-1]

fac[5]

Notice that, during evaluation, "fac[5]" becomes "5 fac[4]", which becomes "5 4 fac[3]" (multiplication understood where spaces occur), which, after a few more iterations, becomes "5 4 3 2 fac[1]", at which point the specific definition is used, and we have "5 4 3 2 1", which Mathematica simplifies to "120".

A function which is helpful in determining how a user-defined function operates is "Trace[]".  "Trace[]" displays the progress of execution of a function by returning a list of the successive evaluations and simplifications used to reach the final answer.  For instance, consider the successive evaluations of "Apply[Plus,{1,2,3,4,5}]]":

Trace[Apply[Plus,{1,2,3,4,5}]]

First Mathematica reduced the command to "1+2+3+4+5", and then it performed the addition operations and reached "15".  Now we use "Trace[]" to examine the successive evaluations when we execute "fac[3]":

Trace[fac[3]]

First Mathematica reduced the command to "3 fac[3 - 1]".  Then, separately, it evaluated "3 - 1".  (The fact that a list appears inside the original list indicates the separate evaluation.)  In evaluating "3 - 1", Mathematica reduced the expression to an addition, "-1 + 3", and added to yield "2".  Then Mathematica expanded "fac[2]", first by using the definition of "fac[]" to produce "2 fac[2 - 1]", then evaluating "2 - 1" to produce "1".   At this stage Mathematica evaluated "fac[1]", using the specific definition, which results in "1".  Then Mathematica substituted "1" for "fac[1]" in "2 fac[1]", yielding "2", and substituted "2" for "fac[2]" in "3 fac[2]", yielding "6", which became the final result.

If we are interested only in the successive invocations of "fac[]", we can instruct "Trace[]" to take out all steps that do not involve the expression "fac".  We do so by specifying "fac" as the second parameter to "Trace[]":

Trace[fac[3],fac]

Now pause for a moment and consider the result of the expression "fac[2.5]".  What problem would arise?  What about "fac[-3]"?

These examples should indicate our function "fac[]" is an excellent candidate for data type checking.   A good solution to the problem of implementing a factorial function might be the following:

Clear[fac];
fac[1] = 1;
fac[n_?((IntegerQ[#]&&(#>0))&)] := n fac[n-1];
fac[n_] := Print["The argument \"",n,
	"\" is not a positive integer."]

fac[-5]

fac[5]

Writing Readable Code: Comments, Usage Lines, and Style

As we create progressively more complicated code, keep in mind that, in many situations, the audience for your programming "composition" is not simply your machine; it may also include other programmers.  Programs are more easily modified and improved by others if the code is initially composed to be readable and modular.  Writing readable code can be accomplished by improving the code itself, and by using comments and usage lines.

Using Boolean Tests and Automatic Data Type Checking

Recall that our last version of "fac[]" includes a rather complicated boolean test:

Clear[fac];
fac[1] = 1;
fac[n_?((IntegerQ[#]&&(#>0))&)] := n fac[n-1];
fac[n_] := Print["The argument \"",n,
	"\" is not a positive integer."]

This code could be improved by highlighting the fact that "n" needs to be an integer, away from the boolean test.  We can do so because Mathematica allows the use of both a data type check and a boolean test together.  The data type must be placed between the underscore and the following question mark, finally followed by the boolean test.  In the following example, using "_Integer?((#>0)&)" instead of "_?(IntegerQ[#]&&(#>0))&" makes our "fac[]" function easier to read.

Clear[fac];
fac[1] = 1;
fac[n_Integer?((#>0)&)] := 
			n fac[n-1];
fac[n_]:= 
			Print["The argument \"",n,
	  "\" is not a positive integer."]

fac[-5]

fac[5]

Comments, Usage Lines

Comments

Comments are a wonderful way of making a function readable.  A comment can be inserted anywhere within a cell or program and is formed by prepending the comment (any sequence of symbols) by "(*" and appending it with "*)".  In general, a judicious but not over-zealous use of comments can greatly improve a function.  In our factorial function, we might add comments thus:

(* factorial function, using recursion *)

(* fac[n]=n fac[n-1], with base case fac[1]=1 *)

Clear[fac]; 

fac[1] = 1;

fac[n_Integer?((#>0)&)] := n fac[n-1];
			
fac[n_]:=  (* if n is not a positive integer *)
	Print["The argument \"",n,
	  "\" is not a positive integer."]

Usage Lines

A Mathematica feature which complements internal comments is the provision of a "usage line" for the function.  Recall that executing "?function" when "function" is a Mathematica function yields a nice description of the function, while if we have previously defined "function", then only our definition of the function is returned.  We can instruct Mathematica to return a description for our function by providing a string which describes the function and indicating that this string should be the usage line. Once we do so, the user can either ask for the usage line ("?function") or insist on the full definition (using "??function").  Let's add a usage line for our factorial function:

(* factorial function, using recursion *)

(* fac[n]=n fac[n-1], with base case fac[1]=1 *)

Clear[fac]; 

fac::usage=
	"fac[n] computes n! for positive integers n" ;

fac[1] = 1;

fac[n_Integer?Positive] := n fac[n-1];
			
fac[n_]:=  (* if n is not a positive integer *)
	Print["The argument \"",n,
	  "\" is not a positive integer."]

(Note that we also replaced the anonymous function "((#>0)&)" with the Mathematica function "Positive[]", which performs the same operation.)

?fac

??fac

Summary: Programming Style

Good programming style incorporates the following guidelines, as well as many others.  To write code well, keep each of these in mind: 
	(1) Use comments whenever the code might be unclear to the reader.  
	(2) Write a usage line which explains your function.  
	(3) Keep all intermediate results local, and control the side effects of your functions.  
	(4) Don't allow a user to execute your function with bad data; check for the data before executing a particular definition.

An Alternative to Boolean Parameter Tests:  Condition Notation

Suppose we wish to define a function "step[]" with one parameter, "x", which is equal to one for all x>2 and equal to -.5 for all x<=2.  Using anonymous functions for boolean tests, we could write the following:

Clear[step];
step[n_?((#>2)&)] := 1;
step[n_?((#<=2)&)] := -0.5;

step[3]

step[-4]

Mathematica provides yet another way to express conditional evaluation, however; we can place what is called a condition immediately following an underscore or a data type check.  Mathematica will then use the specified definition only if the conditions on the parameters are valid.  The syntax of a condition requires the placement of a boolean expression (usually involving the parameter) after the symbols "/;". (To place conditions after more than one argument, place the "\;" followed by the condition after the underscore or data type check and before the comma separating the parameters, as in "a_ \; a>1, b_ \; b<2".)  Using conditions, we have the following alternate solution:

Clear[step];
step[n_ /; n > 2] := 1;
step[n_ /; n <= 2] := -0.5;

step[3]

step[-4]

At this stage we may want to add a data type check.  We would like to constrain the function so that the value of the parameter must be a number, and we could use "NumberQ[]" as part of our condition to test this fact.  However, this method will not incorporate all of the cases we would like:  we would like to be able to compute "step[Pi]", even though "NumberQ[Pi]" is false.

step[Pi]

What we will do instead is find the value of "N[]" applied to the parameter, and then test whether or not this new value is a number.  If so, the "step[]", function will return the appropriate value; if not, then it will return an error message.  We will also add a usage line and a comment.

Clear[step]; (* step function *)

(* step[x]=1 if x is greater than 2;
   step[x]=-0.5 if x is less than or equal to 2;
   step returns an error message if x does not
   reduce to a number *)
   
step::usage = "step[n] returns 1 if n is greater than
2 and -0.5 is n is less than 2";

step[n_ /; NumberQ[N[n]]&&(N[n]>2)] := 1;

step[n_ /; NumberQ[N[n]]&&(N[n]<=2)] := -0.5;

step[n_] := Print["Argument \"",n,"\" is invalid."];

Structured Patterns

Sometimes a programmer knows that the structure of a parameter extends beyond a simple data type or arithmetic value; indeed, the structure might always be a list with three elements. When this is the case, and the programmer wants to use each element separately, Mathematica provides a way to name each of them as parameters, using "structured patterns".  A structured pattern is a parameter which is not a single data type but a specified, more complex structure, with parameters inside the pattern.

Suppose we wish to define a function "switchTwo[]", which interchanges the first two elements of a list with three elements, {x,y,z} (also called a triple).  Without a structured pattern, we might do the following:

Clear[switchTwo]
switchTwo[triple_] :=
   {triple[[2]], triple[[1]], triple[[3]]}

switchTwo[{1,2,3}]

If we wanted insure that the value of the parameter was in fact a list with exactly three elements, we might go a bit further:

Clear[switchTwo];
switchTwo[triple_?((ListQ[#]&&Length[#]==3)&)]:=
	{triple[[2]], triple[[1]], triple[[3]]};
switchTwo[triple_] := 
   Print["Needs a list of three elements."];

switchTwo[{1,2,3}]

However, with a structured pattern, we can more compactly write the parameter as "{x_, y_, z_}", with the three (sub-) parameters inside.  Mathematica will then check for an argument which matches this one exactly---a list with three elements (of any type).

Clear[switchTwo];
switchTwo[{x_,y_,z_}]:= {y,x,z};
switchTwo[n_] := 
   Print["Needs a list of three elements."];

switchTwo[{1,2,3}]

This idea can be used to great advantage when we want to refer to specific parts of expected input parameters.  In a previous section we considered defining a function to determine the difference between the x and y-coordinates of a point {x,y}.  Without a structured pattern, we might use the following definition:

Clear[xyDiff]
xyDiff[pt_]:= Abs[ Last[pt] - First[pt] ]

With a structured pattern, however, we have a much more readable solution.

Clear[xyDiff]
xyDiff[{x_,y_}]:= Abs[ y-x ]