In the previous chapter two small functions were defined which
performed very similar tasks. The sum' function added the
numbers between 1 and *n*. The sq function added the terms
2*i*-1 for *i* between 1 and *n*. We will distill out the common
parts of both functions and see that they can be used to simplify the
definitions of a family of functions similar to sum' and
sq. The common parts of these two functions are:

- a contiguous range with a lower element and upper element;
- a function which is applied to each element in turn;
- an operator to combine the results; and
- an identity element for the operator.

The function we will define will be called reduce. Here is the task we wish the reduce function to perform.

The function g may be extremely simple, perhaps addition or
multiplication. The function f may also be extremely simple,
perhaps the identity function, `fn
x => x`.

In order to implement this function, we need to decide when the reduction has finished. This occurs when the value of the lower element exceeds the value of the upper element, m > n. If this condition is met, the result will be the identity element e. If this condition is not met, the function g is applied to the value obtained by reducing the remainder of the range and f n.

We would like the structure of the implementation to reflect the structure of the analysis of termination given above so we shall implement a sub-function which will assess whether or not the reduction has finished. The scope of this definition can be restricted to the expression in the body of the function.

valreduce =rec(g,e,m,n,f) =>fnletfinished =valtrue => e | false => g (reduce(g, e, m, n-1, f), f n)fnfinished (m>n)in;end

The Standard ML language has the property that if all occurrences in a
program of value identifiers defined by nonrecursive definitions are
replaced by their definitions then an equivalent program is obtained.
We shall apply this expansion to the occurrence of the
finished function used in the reduce function as a way
of explaining the meaning of the **let** .. **in**
.. **end** construct. The program which is produced after
this expansion is performed is shown below.

valreduce =rec(g,e,m,n,f) => (fntrue => e | false => g (reduce(g, e, m, n-1, f), f n)) (m>n);fn

The two versions of reduce implement the same function but obviously the first version is much to be preferred; it is much clearer. If the finished function had been used more than once in the body of the reduce function the result after expansion would have been even less clear. Now we may redefine the sum' and sq functions in terms of reduce.

sum' =valn => reduce (fn(x, y) => x+y, 0, 1, n,fnx => x);fnsq =valn => reduce (fn(x, y) => x+y, 0, 1, n,fnx => 2*x-1);fn

Note that the function
**fn** (x, y) => x+y
which is
passed to the reduce function does nothing more than use the
predefined infix addition operation to form an addition function.
Standard ML provides a facility to convert infix operators to the
corresponding prefix function using the **op** keyword. Thus the
expressions (**op** +)
and **fn** (x, y) => x+y
denote the same function. We will use the **op**
keyword in the definition of another function which uses
reduce, the factorial function, fac. The factorial of *n* is simply
the product of the numbers from 1 to *n*.

fac =valn => reduce (fn*, 1, 1, n,opx => x);fn

Notice that if it is parenthesized, ``(**op** * )''
must be written with a space between the star and the bracket to avoid
confusion with the end-of-comment delimiter.