The notion of a higher-order function – that is, a function that operates on other functions – is a fundamental idea in mathematics.
As an easy example, take the concept of differentiation from Calculus. Whereas a "normal" function like sin(x) operates in terms of numbers (ie. pass it a number, and it'll return you a number as a result), the act of taking a derivative is a little different. When we take the derivative of a function, we get back another function.
This is actually an incredible idea. Now not only can we talk about transformations (of numbers), but we can talk about transformations of transformations!
So in yet another of my blog posts about things I've investigated while working my way through the Structure and Interpretation of Computer Programs, we're going to look at this idea of higher-order functions by considering the process of accumulation.
We'll write some procedures for calculating sums and products, and then show how we can abstract away the common process of successively combining new elements with a current total. We'll then go a step further and write a more general procedure for filtered-accumulation, where we only take those elements that satisfy a particular condition.
[The relevant SICP exercises for this one are 1.30, 1.31, 1.32, and 1.33.]
We're gonna be using good old Java today. In fact, this topic gives us the perfect opportunity to explore the new functional interfaces and lambda expressions of the latest Java 8 release!
Accumulated Sum
Let's dive right in. We mentioned in the introduction that the derivative operation from Calculus works as a higher-order function; it takes in a function as input, and returns a function as output.
Perhaps another, more pertinent example of a higher-order function is a summation across a range, which we usually represent with the sigma notation in mathematics:
Here we sum up all the f(i) from a and b, ie. f(a) + f(a+1) + f(a+2) + ... + f(b).
Now observe that we can completely identify that summation by its end-points a and b, and the function f that is being applied each time. That is, we could represent it as sum(f, a, b), where f is a function and a, b are integers.
So we have a higher-order function! It doesn't return a function though
– it will in fact return a number for the sum. But it definitely acts upon the function f in the input, so we consider it a higher-order function all the same.
How would we write this in Java code? Well, if we assume for the moment that we can find a suitable means of capturing the function f as a parameter, then our process is simple:
- We start with a (double) result of 0.0. We'll collect the sum total in here as we go.
- For each index i between a and b inclusive, we want to get the value of the function f at i (ie. f(i)) and add it to the result.
- We return the result after we're done.
So that was easy. Actually, our only hiccup with this plan is getting the function f available as a parameter for the procedure.
Why is this such a problem? Unlike Scala, Clojure, Python or Ruby, Java wasn't designed with any functional paradigm constructs. Functions aren't first-class objects in Java. (In fact, functions aren't really even a thing in Java; Steve Yegge's awesome "Kingdom of Nouns" story gives a humorous take on this.)
However, with Java's new 8th edition that was released early last year, we now have access to functional interfaces in the standard library, which will allow us to easily specify the function f in our parameter list!
More precisely, we'll define f to have the type Function<Integer,Double>, ie. a function that takes an Integer as input and returns a Double as output. And that's all we really need to do! (Java's autoboxing will take care of the Integer-int and Double-double primitive conversions for us, as always.)
Then when we call the method, we can use the new lambda expression syntax, as you'll see.
So our code is as follows:
Calling the program from the command line simply sums up between two given numbers. We achieve this with a call to our sum() method, where we pass in a lambda expression
(x) -> (double) x that works like an identity function for us (takes in an int x, converts it to a double, and returns it.)
This simply adds up all the numbers; we're not doing anything fancy with our function just yet.
java Sum 1 100
//> Sum from 1 to 100: 5050.0
java Sum 24 35
//> Sum from 24 to 35: 354.0
Of course, we can use different calls to the sum() method to generate more interesting sums. How about an approximation for Pi? We have Euler's expression for Pi in terms of an infinite sum:
The summation is infinite, but we can cut it off at different points to get approximations for the sum. Then we simply multiply by 6 and take the square root to get our Pi approximation! So let's use our sum() method to do just that:
Math.sqrt(6 * sum((x) -> 1.0 / Math.pow(x,2), 1, 20));
//> 3.094669524113704
Math.sqrt(6 * sum((x) -> 1.0 / Math.pow(x,2), 1, 2000));
//> 3.1411152718364823
Math.sqrt(6 * sum((x) -> 1.0 / Math.pow(x,2), 1, 200000));
//> 3.141587878949823
Here we've used the lambda expression (x) -> 1.0 / Math.pow(x,2) to give us the 1/x2 terms for the sum. As you can see, we do appear to get closer to Pi as we sum up more terms – though the convergence speed isn't anything to write home about.
Accumulated Product
Let's apply this same accumulation idea to multiplication instead. Mathematically, we represent this collected-product analogue using the pi notation:
Here we're multiplying all of the f(i) from a to b, ie. f(a)*f(a+1)*f(a+2)*...*f(b).
Now notice that to calculate the product we're running through the exact same algorithm as for the summation, with only two small changes:
- Instead of adding to the result at each point, we multiply with the result.
- We start with the value of result as 1.0 instead of 0.0.
So our code for that is as follows, and it is strikingly similar to our summation code...
We can compile and run our program from the command line to find products, like the product of all the numbers from 1 to 10 (ie. the factorial of 10):
java Product 1 10
//> Product from 1 to 10: 3628800.0
But let's look at something a little more involved. Here's a Pi approximation from the mathematician John Wallis that we can write as an accumulated product:
So we can implement this in Java code by defining a separate method g() to calculate the value of g(x) as given above. We'll run it a few times to get some more approximations for Pi:
public static double g(int x) {
if (x % 2 == 0) {
return ((double) (x+2))/(x+1);
}
else {
return ((double) (x+1))/(x+2);
}
}
4 * product((x) -> g(x), 1, 20);
//> 3.2137849402931877
4 * product((x) -> g(x), 1, 2000);
//> 3.142377365093862
4 * product((x) -> g(x), 1, 200000);
//> 3.1416005075023814
So we do appear to have a Pi approximation method here, though once again we converge very slowly.
The More General Accumulation Procedure
It's a little annoying that those two code snippets are almost identical, isn't it? In fact it was literally a copy-paste job! This suggests to us that there is a pattern there that we can isolate, and we ought to code that up instead. Then we can write sum() and product() as special cases of this more general computation.
The common pattern is the idea of accumulation. In both of these methods, we're running through the exact same steps to generate the total between the end-points, evaluating the function as we go. The only things that ever change are:
- we use a different operator to combine the new value with the existing result,
- we use different null-values for the initial value of the result before we've done anything.
So we should refactor our code into an accumulate() method that works entirely in terms of the abstract notions of 'operator' and 'null-value'. We can do this by adding some more parameters.
The parameter for the null-value will simply be a double, so that's easy. But our operator parameter will be a function – specifically, it will be a function that represents a binary operation that takes two doubles as input and returns a double as output. From our Java 8 functional interfaces, we can use the BinaryOperator<Double> type to give us exactly what we need.
Then when we've coded up our accumulate() method, we can rewrite the sum() and product() methods in a short and simple way by making use of our accumulation abstraction!
Our sum() and product() methods work just like they did before:
sum((x) -> (double) x, 1, 100);
//> 5050.0
product((x) -> (double) x, 1, 10);
//> 3628800.0
But this time, we can also accumulate some different things! How about collecting the successive exponentiation of 2 for powers between 6 and 8? (ie. 2^6^7^8?)
accumulate((x,y) -> Math.pow(x,y), 2.0, (x) -> (double) x, 6, 8);
//> 1.3998404638611276E101
Or how about something a little more exotic: let's accumulate the concatenation of the numbers between 4 and 9, and return that as a double (ie. 456789)?
public static double concat(double x, double y) {
int xIntegralPart = (int) x;
int yIntegralPart = (int) y;
String concatenation = xIntegralPart + "" + yIntegralPart;
return Double.valueOf(concatenation);
}
accumulate((x,y) -> concat(x,y), 0.0, (x) -> (double) x, 4, 9);
//> 456789.0
Obviously we're a little bound by the fact that our method was written to work with doubles. If we wanted to, we might want to look into making the accumulation method even more general, by getting it to play nice with all sorts of data types!
But for now, we can appreciate that we can already express many different computations in terms of this accumulate() method. The abstraction allows us to deal with the notion of "accumulating" something directly, without having to worry about any of the details of how the accumulation actually happens.
A Step Further: Filtered Accumulation
As one last example for today, let's consider the following idea. What if we didn't want to use all of the numbers between the end-points, but only some of them? For instance, say we only wanted to operate on the even integers in the range?
We can make this work by going even further with our abstraction, and considering our accumulate() procedure to be yet another special case of a more general method of computation. The more general procedure will let us pick which elements we want to contribute to the result. (So then accumulate() is just the case where we picked all of the elements.)
This is easy enough to implement. We just add another parameter for a function 'predicate' that tests the current integer in the range and returns a Boolean true/false value. Then our filteredAccumulate() method looks exactly like our accumulate() one, but we only add to the result when the given predicate holds true.
With that method written up, we can then make filteredSum() and filteredProduct() methods that accumulate the sum (or product) of the numbers between the end-points only if the numbers satisfy the predicate.
So our methods, along with some example code, is as follows:
So we can find the sum of the squares of the even numbers between 1 and 20 as follows:
filteredSum((n) -> n % 2 == 0, (x) -> (double) x * x, 1, 20);
//> 1540.0
Similarly, the product of the odd numbers between 6 and 14 can be easily calculated.
filteredProduct((n) -> n % 2 != 0, (x) -> (double) x, 6, 14);
//> 9009.0
Programming in terms of abstractions is an incredibly important notion, in particular for managing the complexity of programs. In the functional paradigm, creating and calling higher-order functions helps us to do exactly this!
As we've seen, higher-order functions allow us to express concepts like "the sum from i = a to b of f(i)" directly in code without having to get down at the level of coding the loop ourselves – in a way completely analogous to a mathematician's use of the sigma notation for the same concept.
No comments:
Post a Comment