Demystifying Rules

Have you ever wondered in what order Mathematica applies replacement rules or why Mathematica sometimes applies a replacement rule and other times doesn't? This article explains how replacement rules work and why they are useful.

Copyright Notice

Copyright 1997 Variable Symbols, Inc.
All rights reserved.  You may distribute this Notebook to others as long as this copyright notice appears at the top of the Notebook.
Variable Symbols, Inc.
6537 Chabot Road
Oakland, CA  94618-1618
Fax: +1 510 652 8461
Tel: +1 510 652 8462
Email: info@VariableSymbols.com
www.VariableSymbols.com

The Big Picture

These notes are intended to be used in conjunction with Nancy Blachman's book Mathematica: A Practical Approach (Prentice-Hall).

Have you ever wondered in what order Mathematica applies replacement rules or why Mathematica sometimes applies a replacement rule and other times doesn't?  In this talk, Nancy will explain how replacement rules work in Mathematica and why she and other Mathematica users find them so useful.

Transformation Rules

Rules are a mechanism for replacing a variable with a value in an expression.  The operator  /. (no space between the / and the .) or ReplaceAll applies a rule or list of rules after evaluating the expression.  Think of /. as meaning given that and -> (a minus sign together with a greater than sign, no space in between the two) as meaning goes to.  So the expression 2x+3y/.x->5b can be interpreted as 2x+3y given that x goes to 5b.

Clear[x, y]2 x + 3 y /. x -> 5 b

Notice that all x's in the expression to the left of /. are replaced by 5b, but that x has not been assigned a value.

x

Predict the output for the following commands. Figure out the order in which rules are evaluated. Which are applied first?

*

2 x + 3 y /. {x -> 7, 3 y -> 5 a}

Explanation

This one is straightforward.  The symbol x gets replaced by 7 and expression 3y gets replaced by 5a, so the expression 2x + 3y gets transformed to 2 * 7 + 5a, which evaluates to 14 + 5a.

#

2 x + 3 y /. {x -> a, 2 x -> b}

Explanation

Mathematica uses a greedy algorithm.  It looks for the largest expression that matches a pattern. First Mathematica checks whether there is a rule that matches the entire expression. If not, it checks whether there is a rule that matches part of an expression.  In this case, there is a rule (2x -> b) that matches part of the original expression 2x + 3y and so that replacement rule is applied.  Another way to look at this is, Mathematica matches the most specific expression, i.e., the rule 2x->b is more specific than the rule x->a.

%

2 x + 3 y /. {x -> a, x -> b}

Explanation

Rules of equal specificity are applied from left to right. So the rule x->a is applied before x->b.

!

2 x + 3 y /. {x -> b, x -> a}

Explanation

Rules of equal specificity are applied from left to right. So in this case, the rule x->b is applied before x->a.

->

2 x + 3 y /. {x -> b, 2  x -> a}

Explanation

As I showed in the example labelled with a #,  Mathematica uses a greedy algorithm. The rule 2x -> a is applied because it matches a larger piece of the entire expression than the rule x -> b.

&

2 x + 3 y /. {{x -> a}, {x -> b}}

Explanation

When Mathematica is given a list of lists of rules, each sublist is applied to the original expression.  The result is a list of transformed expressions.

^

2 x + 3 y /. {{x -> b}, {x -> a}}

Explanation

Each sublist is applied in the order it was specified, i.e., from left to right.

+

1/Sqrt[x^2]  /.  Sqrt[x^2]  ->  9

Explanation

Since Mathematica doesn't know anything about x^2 (whether it is positive or negative), it leaves the expression Sqrt[x^2] unchanged. Mathematica internally represents 1/Sqrt[x^2] as (x^2)^-(1/2) and Sqrt[x^2] as (x^2)^(1/2).

FullForm[1/Sqrt[x^2]]

FullForm[Sqrt[x^2]]

Consequently Mathematica can't find expression Sqrt[x^2] in the original expression 1/Sqrt[x^2].  So the rule isn't applied and so Mathematica returns the original expression unchanged.

=

Sqrt[x]  +  1/Sqrt[x]  /.  {Sqrt[x]  ->  a,  x  ->  b}

Explanation

This is just a slightly more complicated version of the previous problem. Because Sqrt[x] doesn't appear in the expression 1/Sqrt[x], the first rule (Sqrt[x]->a) is only applied to the first element of the sum (Sqrt[x]). The second rule (x->b) is applied to the second element (1/Sqrt[x]).

-

{1,  11,  111,  1111}  /.  {1  ->  one}

Explanation

Numbers are atomic expressions and can't be subdivided.  The rule 1 -> one is applied only when 1 matches the entire number.

"

{1/2,  1  +  I,  1 + i}  /.  {1  ->  one}

Explanation

Numbers, whether they're integers, fractions (1/2), or complex (1 + I), are atomic expressions and can't be subdivided.  The rule 1 -> one is applied only when 1 matches the entire number or when it matches part of an expression.  The expression 1+i may look like a complex number to you, but Mathematica considers it a sum with two elements, the number 1 and the symbol i, which is not interpretted as the Sqrt[-1].  It is just a symbol like x or y.  All constants known to Mathematica begin with capital letters. The Sqrt[-1] is represented by the symbol I (letter Capital i).

FullForm[1  + I]

FullForm[1  + i]

$

2 x + 3 x /. {2 x -> y, 3 x -> 3}

Explanation

Mathematica evaluates the expression to the left of the /. before applying any of the rules.  The expression 2x+3x evaluates to 5x and then none of the rules match so they aren't applied.

-

2 x + 3 y /. {2 x -> a, a -> b}

Explanation

Mathematica applies only those rules that apply to the original expression, so 2x gets replaced by a.  It doesn't look at the result of the substitution. No other rule applies to the original expression.

@

2 x + 3 y //. {2 x -> a, a -> b}

Explanation

The notation //. is an alias for ReplaceRepeated.  The rules are applied repeatedly until there are no more rules that apply. On the first pass, 2x gets replaced by a.  On the second pass a gets replaced by b.

;-)

{a, b, c,  d}  /.  {a  ->  b,  b -> c,  c -> b,  d -> a}

Explanation

The symbol a gets replaced by b, the symbol b gets replaced by c, and the symbol c gets replaced by d, and symbol d gets replaced by a.

~

{a,  b}  //.  {a ->  b,  b -> a}

{a,  b,  c}  //.  {a ->  b,  b -> c,  c ->  a}

{a, b, c,  d}  //.  {a  ->  b,  b -> c,  c -> d,  d -> a}

Explanation

The rules are applied repeatedly. After applying the result many many times, Mathematica stops so that it won't get caught in an infinite loop.

Using Rules

Let's look at some examples of functions that return results in terms of rules.  Solve finds the solutions to a polynomial of equation of degree four or less (as well as some polynomial equations of higher degree). The solution is stated in terms of a list of replacement rules.

soln  =  
      Solve[x^3  -  3  x^2  -  17  x  +  51  ==  0,  x]

We can get a list of the values for x as follows.

x  /.  soln

FindRoot and DSolve also return solutions in terms of relaplcement rules.

FindRoot[Sin[x]/x, {x, 3, 4}]

DSolve[y''[x]+2 y'[x]==0,y[x],x]

What is the Absolute Value of each Root?

Find the complex roots of the polynomial p.

p = (x^10) + (x^9) - (x^7) - (x^6) - (x^5) - (x^4) - (x^3) + x + 1;

complexRoots = NSolve[p == 0]

We compute the absolute value of the roots.

Abs[x] /. complexRoots

What do the absolute value of the complex roots have in common?

Naming Parts of Expressions

Rules provide a mechanism for assigning names to parts of an expressions and then specifying what to do with some or all the names.

nationalDebt
       = {{1900, 1263}, {1930, 16185}, {1960, 284093}, {1990, 3233313}};

ListPlot[nationalDebt, PlotJoined -> True];

The notation year_ is a named pattern that designates a Mathematica expression.  The rule {year_,debt_}:>{year,Log[debt]} specifies that given a pair of values, Mathematica assigns the name year to the first element and debt to the second element in the pair, and returns the pair {year,Log[debt]}.

nationalDebt /. {year_, debt_}  -> {year, Log[debt]}

ListPlot[%, PlotJoined -> True];

Actually, we didn't need to do that because there's a function for making log plots.

Needs["Graphics`Graphics`"]LogListPlot[nationalDebt, PlotJoined -> True, 
      GridLines -> Automatic];

Predict the output for the following commands before looking at the output.

%

{{1, 2,  3}, {4, 5, 6}} /. {x_, y_,  z_} -> {x,  Log[y]}

Explanation

Triples are replaced by pairs.

+

{{1, 2}, {3, 4}, {5, 6}} /. {x_, y_} -> {y,  x}

Explanation

The rule swaps the elements in each pair.

!

{{1, 2,  3}, {4, 5, 6}} /.  {x_, y_} -> {y,  x}

Explanation

The elements in a pair get swapped.  There is only one pair in the expression.

@

{{1, 2}, {3, 4}, {5, 6}} /. {x_, y_} -> {x, Log[y]}

Explanation

Each pair gets replaced by another pair consisting of the first element and the log of the second element.

#

{{1, 2}, {3, 4}} /. {x_, y_} -> {x, Log[y]}

Explanation

The largest pair (outer most) gets replaced by another pair consisting of the first element and the log of the second element. Because Log is Listable, Log of a list evaluates to list consisting of Log of each element in the list.

Log[{3, 4}]

$

f[a]  +  f[b  +  f[c]]  /.  f ->  g

Explanation

The symbol f gets replaced by g.

^

f[a]  +  f[b  +  f[c]]  /.  f[x_]  ->  g[x]

Explanation

Mathematica uses a top down algorithm; it looks for the largest subexpressions that matches the rule.  It find that the expression f[b+f[x]] matches and replaces the head of that expression with g. It doesn't look deeper in the expression. It doesn't look for any more opportunities to apply the substitution.

&

f[a]  +  f[c  +  f[b]]  //.  f[x_]  ->  g[x]

Explanation

Mathematica repeatedly replaces f with g until it can find no more f's.

*

Log[x]  +  Log[y  +  Log[z]]  /.  Log[w_]  ->  w

Explanation

Only when head of an expression or of a subexpression is Log is it replaced.   So the rule doesn't get applied to the nested call to Log.

=

Log[x]  +  Log[y  +  Log[z  +  Log[t]]]  /.  
      Log[w_]  ->  w

Explanation

Only when head of an expression or of a subexpression is Log is it replaced.   So the rule doesn't get applied to the nested calls to Log.

Example: A List of Values

Rules can be used to specify a correspondence between symbols and values.  Notice that the solution to Solve indicates what variable should be set to what value to obtain a solution.

Solve[{2 x + 3 y == 27, 7 x + 5 y == 34}]

DispersionReport returns many statistics.

Needs["Statistics`DescriptiveStatistics`"]dReport = DispersionReport[{3, 7, 2, 3, 1, 2, 8}]

We can pick out a particular result or several results from the list.

MeanDeviation /. dReport

{Variance,  StandardDeviation}  /.  dReport

Delayed Rules

The notation -> is the alias for the function Rule. The notation :> is the alias for the function RuleDelayed. The notation x->Random[] specifies a rule to replace x with the evalutated Random[]. The expression Random[] evaluates to a random number. The notation x:>Random[] specifies a rule to replace x with the unevaluated expression Random[].

Table[x, {3}]

Table[x, {3}]  /.  x -> Random[]

Table[x, {3}]  /.  x :> Random[]

Delayed rules are like delayed assignments in that the right side of the rule is evaluated after the replacement has been made.

Using Trace, you can see the order in which Mathematica evaluates these expressions. With an immediate assignment, Mathematica first replaces Table with a list of three xs. Then Mathematica calls Random and obtains a value. Then each x in the list is replaced by that value.

Table[x, {3}]  /.  x -> Random[]  //  Trace  //  ColumnForm

With a delayed assignment, Mathematica first replaces Table with a list of three x's. Then Mathematica replaces each x in the list with a call to Random. Then Mathematica evaluates each call to Random.

Table[x, {3}]  /.  x :> Random[]  //  Trace  //  ColumnForm

How Mathematica ``does'' Algebra

Mathematica has rewrite rules.  Let's look at some of the rules for performing trigonometric simplifications.  Mathematica looks for expressions that involve terms shown on the left hand side of these transformation rules and rewrites the expressions as specified in the right hand side of the rule.

You can specify rules to transform sums of angles.

\(sumsOfAngleRules\ 
       = {
\ \ Sin[x_\  + \ y_]\  :> \ Sin[x]\ Cos[y]\  + \ Sin[y]\ Cos[x], 
        
\ \ Cos[x_\  + \ y_]\  :> \ Cos[x]\ Cos[y]\  - \ Sin[x]\ Sin[y], 

        \ \ Tan[x_\  + \ y_]\  :> \ 
          \((Tan[x]\  + \ Tan[y])\)/\((1\  - \ Tan[x]\ Tan[y])\)\ }\)

(* half angle args *)
Tan[x_/2] :> (1 - Cos[x])/Sin[x],
Cos[x_/2]^(n_Integer?EvenQ) :> ((1 + Cos[x])/2)^(n/2),
Sin[x_/2]^(n_Integer?EvenQ) :> ((1 - Cos[x])/2)^(n/2),
Sin[x_/2]^n_. Cos[x_/2]^m_. :> Tan[x/2]^n           /; m == -n,
Sin[r_ x_.] Cos[r_ x_.]     :> Sin[2 r x]/2 /; IntegerQ[2r]

These rules used to be in the standard package Algebra`Trigonometry`. In Version 3, they were incorporated into the Mathematica kernel.

Exercises

1

Write a rule that expands the argument of Sin, but will not expand the term (x+y)^2.

(((x + y))^2) Sin[2 (x + 3 y)] /. rule

2

a)  Why doesn't the rule y z_->y Expand[z] expand the term (x+2)(x-2) in the expression y(x+2)(x-2)?

y (x + 2) (x - 2) /. y z_ -> y Expand[z]

b)  Write a rule that will expand y(x+2)(x-2).

3

Given 5 pairs {{x1,y2},{x2,y2},{x3,y3},{x4,y4},{x5,y5}} and 5 heights {z1,z2,z3,z4,z5}  at those points, construct triplets of the form {{x1,y1,z1},{x2,y2,z2},...,{x5,y5.z5}} using only list manipulation constructs and rules, if you wish.  In your solution, do not use Part ([[ ]]) and/or a function that takes an iterator, such as Table or Do.

4

a) Solve the following equations simultaneously.

{2 x + 3 y + 4 z == 34, 4 x + 2 y + 7 z == 42, 
      9 x + 4 y + 5 z == 67}

You should obtain one solution, with values for x, y, and z.  Instruct Mathematica to assign the names x, y, and z to those values.

b) Solve the following equations simultaneously. Remember to clear out the value of x and y if you assigned them values.

{2 x + 3 y == 3, x + 2 (y^2) == 4}

You should obtain two solution, each with values for x and y.  Instruct Mathematica to assign x to a list of two values for x  and y to a list of the two values for y.

5

FactorInteger returns a list of the prime factors of its argument together with their exponents.  For example,

FactorInteger[909]

If you raise the first number in the pair to the power of the second number and then multiply the results together you should obtain the number you factored.

(3^2) (101^1)

Write some Mathematica code that will take the result returned by FactorInteger and check if the result is correct,

FactorInteger[90909]

FactorInteger[9090909]

6

As I mentioned in secion 2.13 on page 37, FindRoot uses Netwon's method to obtain a root, given a function and a starting value.  Produce a plot that contains the curve y=BesselJ[0,x] for x in the range [0, 20] together with seven line segments.  Each of the line segments should have endpoints {x,BesselJ[0,x]} and {r,0} where r in the root returned by FindRoot when given the starting value x. Note:  Using Show you can combine a graph of a function with a line prododuced with the command Graphics.

7

Generate 80 points in three-space.  Plot the points using Show and Graphics3D in color according to their location, so points that are close together should have nearly the same color. For example, here we plot a point and use 1/10th of the value of the x coordinate to specify the amount of red in the point, 1/10th of the y coordinate to specify the amount of green, and 1/10th of the z coordinate for the amount of blue. To make the points more visible, we change the point size by calling PointSize[0.04] before specifying the points.