This post is the second in a series. The first is here. The plan for this post is to introduce just enough notation to define some functions in the Mathematica language, and then use Mathematica to solve a not-entirely-trivial problem.

The central idiom in functional programming is applying a function f to an argument x. Mma offers several notations for doing so. I’ll illustrate the two I use most. By far the most common way to write f applied to x is

f[x]

Notice the use of square brackets, not parentheses. In Mma, parentheses are used to control operator precedence, nothing else. The most common notational alternative to f[x] is

f @ x

This form is nice when chaining a series of functional applications. It is easier to write h @ g @ f @ x than h[ g[ f[x] ] ]. The whitespace is optional; I could have written h@g@f@x. The square bracket notation is more convenient with functions of several arguments.

The next bit of notation illustrates how to define functions. I’ll define a couple of example functions, double and recip. Their meaning should be clear.

double[x_] := 2 * x 

recip[x_] := 1/x 

Notice the underscore following the parameter. It needs to be there. I’ll say more about that shortly. For now just go with it.

Most functional languages put a lot of stock in working with lists. Mma is no different; lists abound. Mma lists are delimited by curly braces, and have comma separated values. Here is a list of integers: {2, 3, 7, 13}. The handy built-in function Range generates lists of integers. For instance, Range[1, 3] returns { 1, 2, 3 }.

One last bit of notation and we are ready to go. Here are two equivalent ways to map the function recip over the elements of a list.

recip /@ Range[1, 3]

Map[recip, Range[1, 3]]

The value of the expression above is {recip[1], recip[2], recip[3]} which is to say { 1, 1/2, 1/3 }.

As an aside, notice that Mma returned exact rational numbers rather than approximate floating point values.

The problem I have chosen as my example is the exercise 8 in Concrete Mathematics, by Graham, Knuth, and Patashnik. Great book, by the way.

The problem is to solve a recurrence. That means that we are given a recursive definition of how to compute the terms of a sequence, and need to figure out an explicit formula for the nth term. You have probably already seen recurrences, even if they weren’t called recurrences. Here’s an easy one, as a warm up.

T0 = 1
Tn = 2 Tn-1

Notice the form of the problem. The first equation is a boundary value which acts as a stopping condition on the recursion described by the second equation. So what does it mean to solve the recurrence? We have to provide an explicit formula for the nth term. A bit of thought will convince you that the solution is

Tn = 2 n

Knuth et alia propose a somewhat harder recurrence. Here it is.

T0 = a
T1 = b
Tn = (1+Tn-1)/Tn-2

How does one start to solve a recurrence? One very natural thing to do is to generate the first few terms of the sequence and look for a pattern. We’ll let Mma do the heavy lifting. Here’s the code.

t[0] := a
t[1] := b
t[n_] := (1 + t[n - 1])/t[n - 2]
 

The code neatly mirrors the mathematics. Notice that the definition of the function t occurs in three parts, rather than as a single expression containing conditional logic. This style of definition is used in other languages, Erlang for instance, and is a joy to use. I really miss it when it is not available.

I promised to say something about the notation of an underscore following a parameter, as after the n in the third clause of the definition of t. Roughly, the underscore indicates that we are using n as a parameter. Without the underscore, we would be defining the action of t on the symbol n. In the first two lines we define t on 0 and 1.

What’s that you say? I did not assign values to a and b? Hold that thought.

Let’s generate a few terms of the sequence. Evaluating t /@ Range[0,4] gives the following:

Yow, continued fractions. Maybe we can simplify those numerators. There’s a handy built-in called Simplify for simplifying algebraic expressions. Let use it. We’ll map Simplify over the previous result by evaluating Simplify /@ t /@ Range[0, 4]. Here’s the result.

That looks better, let’s get a few more terms. Evaluating Simplify /@ t /@ Range[0, 9] we get

The recurrence turns out to be cyclic. There are only five distinct terms which repeat periodically. So the solution is that Tn = Tn mod 5

with T0 = a, T1 = b, etc, as above.

What is x + x ? Algebra says it’s 2x, no matter what the value of x. Most programming languages treat x not as a symbol, but as an identifier for some region of memory, and demand that the memory be initialized. In that world x + x is undefined unless x is given a value. It doesn’t have to be that way. You learned how to work with symbols in grade school. Shouldn’t your computer language be able to do the same?

In Mathematica, a symbol can be assigned a value, or it can just be a symbol. I did not have to give either a or b values to be able to work with algebraic expressions involving a and b. That is a very powerful feature. It makes it possible for Mathematica to perform symbolic mathematics such as calculus. Or simple algebra. For instance, we could expand (a + b +c)^3 as follows:

Expand[(a + b + c)^3]

The result is a^3 + 3 a^2 b + 3 a b^2 + b^3 + 3 a^2 c + 6 a b c + 3 b^2 c + 3 a c^2 + 3 b c^2 + c^3.

The next installment in this series will look at the structure of mma expressions. Lisp, anyone?