Consider the following three functions. The first computes the sum of the integers from a through b:
function sum_integers(a, b) { return a > b ? 0 : a + sum_integers(a + 1, b); }
function sum_cubes(a, b) { return a > b ? 0 : cube(a) + sum_cubes(a + 1, b); }
function pi_sum(a, b) { return a > b ? 0 : 1.0 / (a * (a + 2)) + pi_sum(a + 4, b); }
These three functions clearly share a common underlying pattern. They are for the most part identical, differing only in the name of the function, the function of a used to compute the term to be added, and the function that provides the next value of a. We could generate each of the functions by filling in slots in the same template:
function name(a, b) { return a > b ? 0 : term(a) + name(next(a), b); }
The presence of such a common pattern is strong evidence that there is
a useful abstraction waiting to be brought to the surface. Indeed,
mathematicians long ago identified the abstraction of
summation of a series and invented sigma
notation,
for example
\[ {\sum_{n=a}^{b}\ f(n)=f(a)+\cdots+f(b)\,} \]
to express this concept. The power of sigma notation is that it
allows mathematicians to deal with the concept of summation
itself rather than only with particular sums—for example, to
formulate general results about sums that are independent of the
particular series being summed.
Similarly, as program designers, we would like our language to
be powerful enough so that we can write a
function
that expresses the
concept of summation itself rather than only
functions
that compute particular sums. We can do so readily in our
functional
language by taking the common template shown above and
transforming the slots
into
parameters:
function sum(term, a, next, b) { return a > b ? 0 : term(a) + sum(term, next(a), next, b); }
Notice that sum takes as its arguments the lower and upper bounds a and b together with the functions term and next. We can use sum just as we would any function. For example, we can use it (along with a function inc that increments its argument by 1) to define sum_cubes:
function inc(n) { return n + 1; } function sum_cubes(a, b) { return sum(cube, a, inc, b); }
With the aid of an identity function to compute the term, we can define sum_integers in terms of sum:
function identity(x) { return x; }
function sum_integers(a, b) { return sum(identity, a, inc, b); }
sum_integers(1, 10);
We can also declare pi_sum in the same way:[2]
function pi_sum(a, b) { function pi_term(x) { return 1.0 / (x * (x + 2)); } function pi_next(x) { return x + 4; } return sum(pi_term, a, pi_next, b); }
Once we have sum, we can use it as a building block in formulating further concepts. For instance, the definite integral of a function $f$ between the limits $a$ and $b$ can be approximated numerically using the formula \[ \int_{a}^{b}f = \left[ f\left( a+\frac{dx}{2} \right) + f \left(a+dx+\frac{dx}{2} \right) + f \left( a+2dx+\frac{dx}{2} \right)+\cdots \right] dx \] for small values of $dx$. We can express this directly as a function:
function integral(f, a, b, dx) { function add_dx(x) { return x + dx; } return sum(f, a + dx / 2, add_dx, b) * dx; }
integral(cube, 0, 1, 0.01);
integral(cube, 0, 1, 0.005);
function inc(k) { return k + 1; } function simpsons_rule_integral(f, a, b, n) { function helper(h) { function y(k) { return f((k * h) + a); } function term(k) { return k === 0 || k === n ? y(k) : k % 2 === 0 ? 2 * y(k) : 4 * y(k); } return sum(term, 0, inc, n) * (h / 3); } return helper((b - a) / n); }
function sum(term, a, next, b) { function iter(a, result) { return ?? ? ?? : iter(??,??); } return iter(??, ??); }
function sum(term, a, next, b) { function iter(a, result) { return a > b ? result : iter(next(a), result + term(a)); } return iter(a, 0); }
//recursive process function product_r(term, a, next, b) { return a > b ? 1 : term(a) * product_r(term, next(a), next, b); } //iterative process function product_i(term, a, next, b) { function iter(a, result) { return a > b ? result : iter(next(a), term(a) * result); } return iter(a, 1); }
accumulate(combiner, null_value, term, a, next, b);
//recursive process function accumulate_r(combiner, null_value, term, a, next, b) { return a > b ? null_value : combiner(term(a), accumulate_r(combiner, null_value, term, next(a), next, b)); } //iterative process function accumulate_i(combiner, null_value, term, a, next, b) { function iter(a, result) { return a > b ? result : iter(next(a), combiner(term(a), result)); } return iter(a, null_value); } function sum_i(term, a, next, b) { function plus(x, y) { return x + y; } return accumulate_i(plus, 0, term, a, next, b); } function product_r(term, a, next, b) { function times(x, y) { return x * y; } return accumulate_r(times, 1, term, a, next, b); }
function filtered_accumulate(combiner, null_value, term, a, next, b, filter) { return a > b ? null_value : filter(a) ? combiner(term(a), filtered_accumulate(combiner, null_value, term, next(a), next, b, filter)) : filtered_accumulate(combiner, null_value, term, next(a), next, b, filter); }