9.5 The Restriction Function

In previous sections we saw several examples of higher-order functions that received functions as arguments. In this section we will look at higher-order functions that produce other functions as result.

Let us start by considering a function that computes the double of a given number:

double(x) = 2*x

We can see that the function double represents a particular case of multiplication between two numbers. More specifically, we say that the function double is a restriction of the function * where the first operand is always 2. The same can be said for the functions that calculate the triple or quadruple of a number.

As a second example, let us consider the natural exponential function \(e^x\), where \(e = 2.718281828459045\) is the base of the natural logarithm (also called Napier’s constant or Euler’s number). This function can be defined in terms of the exponential function \(a^b\):

exponential(x) = 2.718281828459045^x

As we can see, the function exponential uses systematically the same first operant (the base). Once more, it is a restriction of a function that uses variable operands.

This type of restriction, where an operation between two operands always uses the same first operand, is a pattern that can be easily implemented using a higher-order function. To better understand the definition of this function, let us first write the two previous functions using anonymous functions:

double = x -> 2*x

exponential = x -> 2.718281828459045^x

By comparing these two anonymous functions, we can tell that the the differences between them are the function used (* in on case and ^ in the other) and the first operand (\(2\) in one case and \(2.718281828459045\) in the other). This suggests that we can define a function that receives these two differences as parameters and produces the corresponding anonymous function:

restriction(f, a) = x -> f(a, x)

Using this function we can now rewrite the double and exponential functions:

double = restriction(*, 2)

exponential = restriction(^, 2.718281828459045)

and use them as any other function:

> double(3)

6

> exponential(2)

7.3890560989306495

The most interesting aspect of the restriction function is that it produces a function as result. That allows it to be used not only to define other functions but also to write simpler expressions. For example, in mathematics we define the n-th harmonic number with the formula:

\[H_n=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}={\sum_{k=1}^{n}\frac{1}{k}}\]

We can define the previous function in Julia using the summation and restriction functions:

harmonic_number(n) = summation(restriction(/, 1), 1, n)

Given that the expression restriction(/, 1) is ought to be repeatedly used, since it corresponds to the multiplicative inverse, it is convenient to name it:

inverse = restriction(/, 1)

And now we can simply write:

harmonic_number(n) = summation(inverse, 1, n)

The restriction function is known in mathematics under the name of currying, in honor of mathematician Haskell Curry. Haskell Curry was a 20th century American mathematician who made important contributions in the field of combinatory logic, collaborated in developing one of the first computers, and described one of the first programming languages.

9.5.1 Exercises 44

9.5.1.1 Question 168

Similar to what we did to define the functions double, exponential, and inverse, use the function restriction to define the functions successor and symmetrical, capable of calculating the successor of a number and the symmetrical value of a number, respectively.

9.5.1.2 Question 169

The restriction function is also useful for defining predicates. Using this function, define the predicate isnegative, which returns true for all negative numbers, and the predicate isone, which returns true only for the number 1.

9.5.1.3 Question 170

Even though the restriction function allows for simplifying the creation of restrictions of functions, it only solves half of the problem, since it produces functions with a fixed first operand. In order to solve the other half of the problem, define the restriction_r function, which fixes the operand on the right.

Use the restriction_r function to define the functions square and predecessor, capable of calculating the square of a number and the predecessor of a number, respectively.