Functions as input parameters

Consider the following problems for computing three different sums.

1. Computing the sum of all integers from $a$ to $b$ (Example 3.12). A functional algorithm for the problem can be given in terms of a function $sum: \mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}$ as
   $$sum(a,b) = \left\{ \begin{array}{ll} 0 & \mbox{if $(a > b)$} \\ a + sum(a+1,b) & \mbox{otherwise} \end{array}\right.$$

2. Computing the sum of squares of all integers from $a$ to $b$. A functional algorithm for the problem can be given in terms of the function $sum\_squares: \mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}$ as
   $$sum\_squares(a,b) = \left\{ \begin{array}{ll} 0 & \mbox{if $(a > b)$} \\ square(a) + sum\_squares(a+1,b) & \mbox{otherwise} \end{array}\right.$$

3. Computing the sum of a sequence of terms in the following series which converges to $\pi/8$:^5.5
   $$\frac{1}{1 \cdot 3} + \frac{1}{5 \cdot 7} + \frac{1}{9 \cdot 11} + \ldots$$
   A functional algorithm for the problem can be given in terms of the function $pi\_sum: \mathbb{N}\rightarrow \mathbb{R}$ as
   $$pi\_sum(n) = \left\{ \begin{array}{ll} 0 & \mbox{if $(a > b)$} \\ (1/(a*(a+2))) + pi\_sum(a+4,b) & \mbox{otherwise} \end{array}\right.$$

Clearly, the three algorithms share a lot in common; so much so that they warrant the design of a common function which combines the common characteristics of the three different different functions. This can be achieved by defining a generic summation whose functionality is given by

$$\sum_{x=a,succ(x)}^b f(x)$$

i.e., the summation of an arbitrary function $f(x)$ in the range $[a,b]$ in steps defined by the successor function $succ(x)$. In order to write a functional algorithm for such a generic summation one needs to be able to accept two functions $f: \mathbb{N}\rightarrow \alpha$ and $succ:\mathbb{N}\rightarrow \mathbb{N}$ as input in addition to the parameters $a$ and $b$ which belong to the set $\mathbb{N}$. Here $\alpha$ may be any generic type on which the operation $+$ is defined (e.g. $\mathbb{N}$ or $\mathbb{R}$). Hence, the generic summation must be a higher-order function whose type is

$$summation: \mathbb{N}\times \mathbb{N}\times (\mathbb{N}\rightarrow \alpha) \times (\mathbb{N}\rightarrow \mathbb{N}) \rightarrow \alpha$$

A functional algorithm for the generic summation can then be given as

$$summation(a,b,f,succ) = \left\{ \begin{array}{ll} 0 & \mbox{if $(... ...} \\ f(a) + summation(succ(a),b,f,succ) & \mbox{otherwise} \end{array}\right.$$

The advantage of defining such a higher-order function independent of any particular problem is that the analysis of correctness and efficiency of the algorithm can be carried out in a general setting.

Exercise 5.13   For the function $summation$

1. Establish the correctness assuming the correctness of the functions $f$ and $succ$. Note that $f$ and $succ$ are just procedural abstractions of two unknown functions.
2. Determine the time and the space complexity in terms of number of calls to the functions $f$ and $succ$.

summation.nw01In ML the higher-order summation function can be written as follows: 2summation fun summation(a:int,b,f,succ) = if (a > b) then 0 else f(a) + summation(succ(a),b,f,succ); > val summation = fn : int * int * (int -> int) * (int -> int) -> int 3 Then the summation functions $sum$ and $sum\_squares$ of the type $\mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}$ can be defined in terms of the higher-order summation function as follows: 4sum fun sum(a,b) = let fun term(x) = x : int; fun next(x) = x + 1 in summation(a,b,term,next) end; > val sum = fn : int * int -> int 5sum_squares fun sum_squares(a,b) = let fun term(x) = x*x : int; fun next(x) = x + 1 in summation(a,b,term,next) end; > val sum_squares = fn : int * int -> int 6 The functions $sum$ and $sum\_squares$ are of the type $\mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}$. In contrast, the function $pi\_sum$ is of the type $\mathbb{N}\times \mathbb{N}\rightarrow \mathbb{R}$. In order to satisfy the strict type checking in ML , we have to re-define the function $summation$ so that it returns a value of the type $\mathbb{R}$. 7real_summation fun real_summation(a : int,b,f,succ) = if (a > b) then 0.0 else f(a) + summation(succ(a),b,f,succ); > val real_summation = fn : int * int * (int -> real) * (int -> int) -> real 8 Note that the only change in code that is required is the replacement of the identity element of summation. We can now define $pi\_sum$ as 9pi_sum fun pi_sum(n) = let fun term(x) = 1.0/real(x*(x+2)); fun next(x) = x + 4 in summation(1,n,term,next)*8.0 end; > val pi_sum = fn : int * int -> real 10 Thus we see that the same form of the abstract function $summation$ can be used to compute sums of various different kinds. It may appear that the same effect may be achieved by defining the summation function directly (not as a higher-order function) as 11summation (incorrect) fun summation(a,b) = if (a > b) then 0 else f(a)+summation(succ(a),b); > Error: unbound variable or constructor: succ, f 12 and by defining a particular summing function, say sum as 13sum (incorrect) fun sum(a:int,b:int) = let fun f(x : int) = x; fun succ(x) = x + 1 in summation(a,b) end; 14 However, this will not work because the functions f and succ are local to the function sum and are not defined in the global scope of the function summation. Both f and succ are free parameters in the scope of the function summation and in order to evaluate the function summation these two functions must be defined in its global scope with the same names. It is not advisable to define the function summation with f and succ as free parameters because then, in order to use the function summation, one has to look inside its definition to find these names and it cannot be used as a black-box. In principle this would be similar to having to open the back panel of a TV with a screw-driver in order to determine whether it has 110V or 220V power input. Clearly, then the TV ceases to be a black-box (at least figuratively speaking).