Functions As Expressions

Mathematica Expressions Representing Functions

Some Mathematica commands expect functions being passed as parameters, e.g.

Sort[{5,2,1,4,3,4}]

Sort[{5,2,1,4,3,4},Greater]

Sort[{{1,2,3},{{a}},{b},{{c},d}}]

Deeper[l1_,l2_]:=Depth[l1]≥Depth[l2]

Sort[{{1,2,3},{{a}},{b},{{c},d}},Deeper]

In these examples, functions were passed as parameters by passing their name. Compare to C/C++, where the function name is identified with a pointer to the function. In Mathematica, however, there is no such concept like pointers. Any symbol can be passed as a parameter to a program and if we consider it to be a function name then we just apply it to arguments.

Compare[x_,y_,comp_]/;comp[x,y]:=x

Compare[x_,y_,comp_]:=y

Compare[3,10,Less]

Compare[3,10,Greater]

Mathematica offers functions as expressions without defining them under a certain name.

f=Function[x,(x^2)]

Expressions with head Function are called pure functions. They can be applied to arguments.

f[3]

Function[x,(x^2)][3]

This is again currying! 
In short form, we can write # as a placeholder for the function variable. Don't forget the & at the end of the expression marking it to be a function.

(((#)^2))&[3]

(((#)^2))&[3]//FullForm

(((#)^2))//FullForm

Similarly, multivariate functions can be expressed as follows:

Function[{x,y},(Sqrt[(x^2)+(y^2)])][3,4]

In short form, we can write #i for the i–th variable and mark the resulting expression as a function using &.

((Sqrt[((#1)^2)+((#2)^2)])&)[3,4]

f=(Sqrt[((#1)^2)+((#2)^2)])&;

f[3,4]

In the example above:

Sort[{1,2,3,4,5,-3,-1},Abs[#1]>Abs[#2]&]

Sort[{{1,2,3},{{a}},{b},{{c},d}},Depth[#1]≥Depth[#2]&]

Of course, functions are just expressions like all other expressions and they can occur even as the return value in a program.

LinearFunction[k_,d_]:=Function[x,k x+d]

LinearFunction[3,7]

LinearFunction[3,7][1]

Function is a scoping construct (like Table, Sum, Integrate, Module, Block) that treats the function variable as a locally bound symbol. Thus, in certain situations, Mathematica renames the bound variable in order to avoid naming conflicts. Moreover,

Attributes[Function]

when manipulating Function–expressions, we need to be aware of the Hold–attribute!

Clear[f]

Applying Functions to Expressions

Standard Function Application

Functions can be applied to expressions in various forms, the easiest being to apply the function to the appropriate number of arguments, i.e.

Function[x,(x^2)][3]

Function[{x,y},(Sqrt[(x^2)+(y^2)])][3,4]

Componentwise Application of a Unary Function

However, we often need to apply functions to expressions in some special way, e.g. componentwise

Map[Function[x,(x^2)],{1,2,3,4}]

Map[(x^2),{1,2,3,4}]

Map[#+4&,{1,2,3,4}]

Moreover, we can specify at which level the function should be applied.

Map[#+4&,{1,{2},{3},4},2]

Try to understand what happens in the previous example!

Map[#+4&,{1,{2},{3},4},{2}]

Application at Specified Positions

expr=f[a,g[23],h[(1/2),p["K[x]",10]]];

Position[expr,_Integer?EvenQ]

MapAt[#/2&,expr,Position[expr,_Integer?EvenQ]]

Componentwise Application Taking into Account the Position

Clear[a,b,c]

Suppose we want to put an index indication the position to every part of an expression.

MapIndexed[f,{a,b,c}]

MapIndexed[(Subscript[#1, #2[[1]]])&,{a,b,c}]

Alternative 1:

PutSubscript[e_,{s_}]:=(Subscript[e, s])

PutSubscript[e_,s_]:=(Subscript[e, s[[1]]])

MapIndexed[PutSubscript,{a,b,c}]

Alternative 2: This variant is even more general. It allows to specify an alphabet from which the respective indices are taken.

IndexAlphabet={"I","II","III"};

MapIndexed[PutSubscript[#1,{Extract[IndexAlphabet,#2]}]&,{a,b,c}]

Alternative 3: we can use MapThread, see next section.

MapThread[PutSubscript[#1,{#2}]&,{{a,b,c},IndexAlphabet}]

Compontwise Application of Binary Function

MapThread[f,{{a,b,c},{1,2,3}}]

MapThread[Equal,{{a,b,c},Range[3]}]

The same can always be established using Inner.

Inner[Equal,{a,b,c},Range[3],List]

Compare:

Thread[Equal[{a,b,c},Range[3]]]

Function Application to Argument–Expression

A different way of function application to an expression is to feed the arguments of the expression as parameters to the function. This can be done using Apply.

Apply[f,{1,2,3,4}]

Often, the expression is a list, but it not necessarily be a list!

Apply[f,g[1,2,3,4]]

Apply[Table,f[(i^2),{i,10}]]

Apply[f,expr] effectively just substitutes the head of expr by f and then evaluates the resulting expression.

Apply[#1-((#2)^2)&,f[1,3]]

More examples:

Apply[Plus,Map[f,Range[5]]]

Apply[Plus,Map[((#)^2)&,Range[5]]]

(∑_(i=1)^5)(i^2)

Iteration Through Repeated Function Application

Mathematica offers some commands that allow to replace iteration by certain variants of function application. Map, MapThread, and MapIndexed were first examples. Similar to Map, just without returning the result, is Scan:

Clear[a,b,c]

Scan[(#=0)&,{a,b,c}]

Map would have the same effect, but it would produce a return value. Of course, we can suppress the return value using ";" or, in a program, we can simply ignore the return value, but I prefer Scan for these purposes.

{a,b,c}

Clear[a,b,c]

Then there is Nest, performs a fixed number of iterations starting with a given value.

Nest[f,x,4]

Nest[#+2&,20,4]

NestList[f,x,4]

Similar to Nest, but without a fixed number of repetitions, is FixedPoint.

FixedPoint[N[Cos[#1]]&,0.5,SameTest->(Abs[#1-#2]<0.0001&)]

FixedPointList[N[Cos[#1]]&,0.5,SameTest->(Abs[#1-#2]<0.0001&)]

Further variations:

Fold[f,x,{1,2,3}]

FoldList[f,x,{1,2,3}]

ComposeList[{f,g,h},x]

NestWhileList[2#&,1,#<150&]

Exercise: FoldRight

Implement a function FoldRight, which, like the  Mathematica–Function Fold, folds a function f from right over a list.

Fold[f,x,{a,b,c}]

results in

f[f[f[x,a],b],c]

FoldRight[f,{a,b,c},x]

should result in:

f[a,f[b,f[c,x]]]

Solution: see separate notebook.

Exercise: Random Walk

Let's consider once more the program RandomWalk from the very beginning. We started with a "procedural implementation" containing to nested Do–loops. The inner loop represented 10 random movements, the outer loop repeated the random walk a fixed number of times in order to approximate the probability for the random walk to stop at {7,3}.
Write a Mathematica program that approximates the probability for the random walk using 10 steps to stop at some position p (input parameter). Implement all "loops" using some variants of repeated function application.

Solution: see separate notebook.

Pure Functions vs. Named Functions

The main difference between pure functions and named functions that are introduced by a function definition is that pure functions lack the possibility of pattern matching in the parameters. Thus, often a powerful combination is to introduce named functions using the full power of pattern matching and then apply these functions appropriately using Map, Apply, and the like, as already demonstrated above. Note, however, that attributes can also be assigned to pure functions.

Unevaluated[{3+5,10!}]

Map[Head,Unevaluated[{3+5,10!}]]

Attributes[Head]

Map[Function[x,Head[Unevaluated[x]],{HoldFirst}],Unevaluated[{3+5,10!}]]

Selecting Parts of Expressions by Property

We already know Cases for selecting parts of an expression that match a certain pattern. Alternatively, we can select parts that fulfill a given test.

expr=f[a,g[23],h[1/2,p["K[x]",10]]]

Select[expr,Length[#]≥2&]

Cases[expr,_g]

Note, that, unlike Cases, the head of the original expression is conserved in the result. Cases always returns a list.

Transformation Rules

Transformation Rules as an Alternative for Functions

Function application is very much related to substitution, i.e. the function application f[a] is computed by substituting a for the function variable in f. If f is introduced through a definition in Mathematica then this substitution happens in the pattern matching process of expression evaluation. If f is a pure function of the form Function[x,body], then f[a] happens to substitute a for x in body and then evaluates the resulting expression.

Clear[a]

Function[x,(x^2)][a]

Thus, when working with functions it is often convenient to just work on the expression defining the function. Instead of Function[x,body] we only consider 'body'. In these situations we need to use the operation of substitution explicitly instead of function application.

ReplaceAll[(x^2),x->a]

a=4;

FullForm[x->a]

Attributes[Rule]

Attributes[ReplaceAll]

Hold[(x^2)]/.x->a

expr=Hold[(x^2)]

Map[((#)^3)&,expr]

Sqrt[3]

x=.

expr/.(x^2)->(x^6)

Attributes[Hold]

With[{x=3},With[{x=x},expr]]//Trace

%[[1]]

Attributes[With]

ReleaseHold[%31]

x

x=3;

Mathematica Expressions Representing Transformation Rules

In fact, when working with Mathematica expressions it is often convenient to perform certain transformations. It is sometimes "easier" to apply a transformation than to apply a certain function performing the transformation. The expression lhs->rhs is called a transformation rule and there are several operations (like ReplaceAll above) for applying transformation rules to expressions. 
Note that pattern matching is available also in the application of transformation rules, i.e. when applying a transformation rule, the left–hand side of the rule may contain pattern expressions and when an expression matches the left–hand side of the transformation rule it is going to be substituted by the respective instance of the right–hand side.

3(x^2)/.(x^(n_?EvenQ))->(z^(n/2))

3(x^2)/.(x^(n_?EvenQ))->(z^(n/2))//Trace

Now imagine you want to represent each even power (x^n) as ((((x^(n/2))))^2). Similar to above, we would use

3(x^4)/.(x^(n_?EvenQ))->((((x^(n/2))))^2)

What happens here?

FullForm[x->a]

FullForm[Hold[3(x^4)/.(x^(n_?EvenQ))->((((x^(n/2))))^2)]]

Attributes[Rule]

Attributes[ReplaceAll]

Now everything is clear! ReplaceAll evaluates the transformation rule before the transformation is actually applied and the transformation rule lhs->rhs evaluates both lhs and rhs, thus

(x^(n_?EvenQ))->((((x^(n/2))))^2)

This rule, of course, is the identical transformation, therefore it has no effect. What we need here is a rule that does not evaluate its right–hand side!

Attributes[RuleDelayed]

FullForm[x:>a]

(x^(n_?EvenQ)):>((((x^(n/2))))^2)

Fine, this is what we wanted.

3(x^4)/.(x^(n_?EvenQ)):>((((x^(n/2))))^2)

Why does it still not work? Think about this before you proceed with the subsequent statements.

3(x^4)/.(x^(n_?EvenQ)):>((((x^(n/2))))^2)//Trace

The rule is applied correctly and it results in 3((((x^2)))^2), which is then evaluated further by the standard Mathematica evaluation loop resulting in 3(x^4).

Hold[3(x^4)]/.(x^(n_?EvenQ)):>((((x^(n/2))))^2)

Note, however, that transformation rules apply inside Hold, so this gives a possibility to modify expressions whose standard evaluation is suppressed by Hold. Note also, that substituting 4/2 by 2 in the expression above might be tricky, since a transformation rule

4/2->2

will always evaluate the left–hand side and there is no variant of a transformation rule that keeps its left–hand side unevaluated. For this purpose one uses HoldPattern as a wrapper for the left–hand side of the rule.

Hold[3 ((((x^(4/2))))^2)]/.HoldPattern[4/2]->2

An expression HoldPattern[patt] keeps 'patt' unevaluated and it behaves like 'patt' for pattern matching.

Attributes[HoldPattern]

Attributes[RuleDelayed]

How to Apply a Transformation Rule to an Expression

There are various possibilities how to actually apply transformation rules to an expression. Replace[expr,rule] applies rule to expr.

Replace[3(x^4),c_ ((b_)^4)->(c^b)]

However, Replace does not apply to subexpressions, i.e. the transformation is only applied to the entire expression as a whole but not to parts of it.

Replace[3(x^4), ((b_)^4)->b]

If we want to apply rules to all possible subparts of an expression, then we should use ReplaceAll or its short infix form /. .

3(x^4)/. ((b_)^4)->b

3(x^4)+5(y^12)+3(z^3)/. c_ ((b_)^(n_?EvenQ))->(c+1)(b^(n/2))

If a subexpression is transformed once then ReplaceAll immediately proceeds with the next subexpression, even if further transformations could be done on the original position. This is why, in the example above, (x^2) and (y^6) are not transformed further. ReplaceRepeated (short infix //.) applies transformations repeatedly to all subexpressions until no further transformation is possible.

3(x^4)+5(y^12)+3(z^3)//. c_ ((b_)^(n_?EvenQ))->(c+1)(b^(n/2))

How to Apply Rules Simultaneously

When applying transformation rules to an expression, we can use a structured list of transformation rules in order to apply more than one rule. The list–structure of the transformation rules influences the way how rules are applied.

3(x^4)+5(y^12)+3(z^3)/.{c_ ((b_)^(n_?EvenQ))->(c+1)(b^(n/2)),c_ ((b_)^(n_)):> (b^(n+1))}

3(x^4)+5(y^12)+3(z^3)/.{c_ ((b_)^(n_))-> (b^(n+1)),c_ ((b_)^(n_?EvenQ))->(c+1)(b^(n/2))}

When applying a list of transformation rules {(Subscript[r, 1]),…,(Subscript[r, n])} to an expression then, at each applicable position (depending on whether being used with Replace, ReplaceAll, or ReplaceRepeated), the first matching rule only is applied.

3(x^4)+5(y^12)+3(z^3)/.{{c_ ((b_)^(n_))-> (b^(n+1))},{c_ ((b_)^(n_?EvenQ))->(c+1)(b^(n/2))}}

When applying a list of lists of transformation rules {(Subscript[list, 1]),…,(Subscript[list, n])} to an expression then the result is a list of expressions having at position i the result of applying (Subscript[list, i]) to the expression. There is also a variant of Replace, which not only applies the first matching rule in a list, but which returns a list containing all possible replacements.

ReplaceList[3(x^4),{c_ ((b_)^(n_))-> (b^(n+1)),c_ ((b_)^(n_?EvenQ))->(c+1)(b^(n/2))}]

ReplaceList[3(z^3),{c_ ((b_)^(n_))-> (b^(n+1)),c_ ((b_)^(n_?EvenQ))->(c+1)(b^(n/2))}]

Note the difference to using a list of lists of transformation rules.

Replace[3(z^3),{{c_ ((b_)^(n_))-> (b^(n+1))},{c_ ((b_)^(n_?EvenQ))->(c+1)(b^(n/2))}}]

Many Mathematica functions return their result in form of transformation rules, in particular Solve and related functions.

"Programming" by Application of Transformation Rules

Repeated application of transformations can be seen as a means for programming. As an example, we can setup some rules for differentiation of an expression as transformation rules. In order to keep things simple, we fix x as the variable for differentiation. Then we write f' for differentiation of expression f w.r.t. x.

((x^3)Sin[x]+2Log[Cos[x]]+(E^x))'/.(f_+g_)':>f'+g'

((x^3)Sin[x]+2Log[Cos[x]]+(E^x))'//.(f_+g_)':>f'+g'

((x^3)Sin[x]+2Log[Cos[x]]+(E^x))'//.{(f_+g_)':>f'+g',((x^(n_)))':>n (x^(n-1)),(c_ f_)'/;FreeQ[c,x]:>c f',(f_*g_)':>f'g+g'f}

The order of the rules in the list matters: Multiplication with a constant must occur before the general product rule.

((x^3)Sin[x]+2Log[Cos[x]]+(E^x))'//.{(f_+g_)':>f'+g',((x^(n_)))':>n (x^(n-1)),(f_*g_)':>f'g+g'f,(c_ f_)'/;FreeQ[c,x]:>c f'}

Find out what happened exactly in this (wrong) computation.

((x^3)Sin[x]+2Log[Cos[x]]+(E^x))'//.{(f_+g_)':>f'+g',((x^(n_)))':>n (x^(n-1)),(c_ f_)'/;FreeQ[c,x]:>c f',(f_*g_)':>f'g+g'f,((E^x))':>(E^x),Log[x]':>1/x,Sin[x]':>Cos[x],Cos[x]':>-Sin[x]}

The chain rule is a little tricky:

(Log[Cos[x]])'/.{Log[x]':>1/x,f_[g_]':>(f[x]'/.x->g)*g'}

Although the right–hand side of the rule does not evaluate (when giving the rule), the result after application evaluates before the next rule is applied, see the details

(Log[Cos[x]])'/.{Log[x]':>1/x,f_[g_]':>(f[x]'/.x->g)*g'}//Trace

After application of the chain rule, we have

((Log[x])'/.x->Cos[x]) (Cos[x])'

and now Log[x]' should be replaced by 1/x before x gets replaced by Cos[x] but unfortunately x is replaced immediately. Note that ReplaceRepeated would end up in an infinite loop always applying the chian rule. We give an additional condition in order to prevent the chain rule from being applied to elementary expressions.

(Log[Cos[x]])'/.{Log[x]':>1/x,f_[g_]':>Hold[f[x]'/.x->g]*g'}

If we now use //. we must be careful still because the left–hand side of the chain rule would apply to elementary expressions, whose differentiation rules are unknown or unspecified, like Cos[x] above. We present two solutions:

(Log[Cos[x]])'//.{Log[x]':>1/x,f_[g_/;Depth[g]>1]':>Hold[f[x]'/.x->g]*g'}

Alternatively, we can give a "special rule" for unknown derivatives before the chain rule. This rule must guarantee to replace the derivative by some expression which cannot be rewritten by the chain rule (or other rules that follow).

(Log[Cos[x]])'//.{Log[x]':>1/x,f_[x]':>ToString[f[x]'],f_[g_]':>Hold[f[x]'/.x->g]*g'}

All this together (still incomplete, of course):

Differentiate[expr_]:=ReleaseHold[expr'//.{((x^(n_)))':>n (x^(n-1)),(c_ f_)'/;FreeQ[c,x]:>c f',((E^x))':>(E^x),Log[x]':>1/x,Sin[x]':>Cos[x],Cos[x]':>-Sin[x],(f_+g_)':>f'+g',(f_*g_)':>f'g+g'f,f_[g_/;Depth[g]>1]':>Hold[f[x]'/.x->g]*g'}]

Differentiate[(x^3)Sin[x]+2Log[Cos[x]]+(E^x)]

D[(x^3)Sin[x]+2Log[Cos[x]]+(E^x),x]

Another nice example is "sorting of lists", which can be done be successively swapping elements that are in the "wrong order".

l=Table[Random[Integer,{1,10}],{i,10}]

l/.{pre___,x_,y_,post___}/;x<y->{pre,y,x,post}

l//.{pre___,x_,y_,post___}/;x<y->{pre,y,x,post}

Special Topic: Evaluation with Hold–Attributes

Suppose we want to generate the expanded form of (∑_(i=1)^10)(i^2), i.e.

(1^2)+(2^2)+(3^2)+…+(10^2)

in Mathematica. 
Write a Mathematica program that returns an expression representing the expanded sum for a summand (above: (i^2)) and a summation range (above: {i,1,10}) given as input to the program.

The problem:

(∑_(i=1)^10)(i^2)

Unevaluated[(∑_(i=1)^10)(i^2)]

FullForm[Unevaluated[(∑_(i=1)^10)(i^2)]]

(∑_(i=1)^10)Unevaluated[(i^2)]

Solution: see separate notebook.

Special Topic: Combining the Features of the Language in a Concrete Example

The Solution of a Linear Diophantine Equation in 2 Variables

A linear diophantine equation in 2 variables is an equation of the form a x+b y==c with a,b,c∈ℤ. We need to find x,y∈ℤ.
Write a Mathematica program that computes all solutions for an equation given as input to the program.
Do not use built in commands for solving equations, lookup a solution formula for diophantine equations in your lecture notes or on the web. Think about the structure of the solutions and choose a mathematically adequate representation in Mathematica. Take care about solvability of the equation, etc.

Solution: see separate notebook.

A Program that Verifies the Solution of a Linear Diophantine Equation in 2 Variables

Write a program that verifies the solution given by the program that solves a given linear diophantine equation in 2 variables.

Solution: see separate notebook.