Copyright (C) 1997 Rich Neidinger, John Swallow, and Todd Will.  Free for
distribution to college and university instructors for personal,
non-commercial use.  If these notebooks are used in a course, the authors
request $20 per student.

Chapter IV.  Pattern Matching in Symbolic Programming

11. Pattern Matching and Conditional Evaluation

Last revision:  September 12 1996

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.

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, anduses 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 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 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 ]