Intro to Functional Programming (with examples in Java) - Part 2

In the previous post, I introduced first-class/higher-order functions, and gave some quick examples. We saw that it's a little tricky in Java to have higher-order functions that can generalize on type parameters, but that we can work around that with some factory method trickery. You still need to make sure that your factory methods are mapping the static type parameters to the raw/erased versions correctly, but at least you can only mess it up in one place.

In this post, we'll look at currying and partial application of functions, as well as two of the more popular higher-order functions in more detail.

Currying and Partial Application

In math, suppose you have a function f(x,y) of one variable. If you want, you can treat the two variables independently, by "fixing" the other parameter and defining a new function of one variable -- e.g. define g(x) = f(x,0) and h(y) = f(0, y).

Suppose you don't know ahead of time what fixed values you want to pick. Say you have a function f(x1, x2, x3, ..., xn) and you define g(x) = f(x, x2, x3, ..., xn). In this case, you "bind" the x variable from g to one of the variables from f, but the remaining variables would be unbound. In this case, g is not a function that returns "values" for each input x, but rather a function that returns functions of n - 1 variables. That is, to get a value, you would need to "call" the function as g(x)(x2, ..., xn) (i.e. you would first bind x, and then you would bind the remaining variables). For a fixed x, we could then define h(x2, ..., xn) = g(x)(x2, ..., xn) = f(x, x2, ..., xn). With the definition I'll use for currying, we have the following properties:

• g is a "curried" version of f. That is, it is a function of one variable that returns functions of n-1 variables.
• h = g(x) is a "partial application" of f. That is, the value x has been "applied" (or bound) to the variable x1, while the remaining n-1 variables remain unbound.

Getting back to our functional programming examples, invoking curry on a FunctionN returns a Function1, which in turn returns a FunctionN-1. Let's look at the somewhat messy code involved in doing this to a Function2:

This turns a function f(x,y) into the equivalent function f(x)(y), where x and y can be applied individually (but only in that order). Here is an example:

Of course, it would be nice to not have to explicitly write the curry() call when we want to bind the parameters one-by-one. (Especially since, for a Function4, for example, the call would turn into f.curry().apply(1).curry().apply(2).curry().apply(3).apply(4). In theory, I could modify my definition of curry to return a chain of Function1s, so you would only need to call it once, followed by the series of applys.) The easy way of doing this is to hide the curry call(s), within an overloaded definition of apply.

Recall that apply for a Function2<R,T1,T2> takes two arguments of type T1 and T2 respectively, and returns a value of type R. We can write an overloaded definition of apply that only takes one argument of type T1 and returns a Function1<R,T2>. Here is the code:

Using this overloaded definition of apply, we can now "partially" apply any function to yield a function that takes one less parameter. The addition example above simplifies to:

We can generalize the currying of Function2 to arbitrary FunctionN, and get partial application "for free", by making them extend a Curryable class defined as follows:

Then for FunctionN, we just need to define a curry function that returns a Function1 that returns a FunctionN-1:

A pair of useful higher-order functions

Recall from the previous post that a higher-order function takes at least one other function as a parameter. The general reason why you want to use higher-order functions is that they provide a logical separation between what you want to do and how it is going to be done. The higher-order function can define the boring/standard "how" and the passed function defines the particular "what" for your problem.

Consider the following example: We have a list of integers, and we want to double each one and return the output in a new list. The process is simple: allocate a new list, iterate over the existing list, storing two times the current value in the new list. Unfortunately, there are several different ways to implement iteration over the list, as shown in the following code:

If you take the time to run this code (or you were looking carefully), you'll find that it has a bug. In doubleListWithIteratorFor, instead of saying iter.next() * 2, I wrote iter.next() + 2. Oops!

The problem, I see it, is that the actual problem I'm trying to solve (doubling each element) has been overshadowed by the way it's being solved (iterating over each element, storing the result in a new list). The action of producing a new list (or collection) by "doing something" to each element of an existing list is very common in software development, with only the "something" varying from case to case.

In the previous post, I described a transformList higher-order function, and the tricks involved with creating one which is type-safe in its generic parameters. This function is more commonly called map in the functional programming world. For a recap and a better generalization of that code, here is the map part of my ListUtils class:

The type parameters of map are explained as follows: map takes as input a function that turns T1s into Rs and a list of T1s, and return a list of Rs. If you give me a device that can turn an apple into an orange, and a bag of apples, then I will give you a bag of oranges. In Haskell, this is written as map :: (a->b) -> [a] -> [b]. The consecutive arrows reflect the fact that all functions in Haskell are curried, so map partially-applied with a function from a to b yields a function that takes a list of a and returns a list of b. I'm introducing the Haskell function signature syntax now, so I can use it to help explain the definition of fold below.

Since the map function nicely handles the "how" of traversing a list and returning the transformation results in a new list, all I need to supply is "what" transformation I want to do, and "what" list I want to use as input. We can solve the list doubling problem from above with the following code:

The anonymous class boilerplate required by Java is a little annoying, but the only "executable" parts of that code are the map call, the return statement, and the apply invocation. In other words, the only executable pieces relate exactly to what I am trying to do (map a function that doubles its input over the list values).

Another common task in software is producing a single value from the contents of a list. This may be finding the min/max value in the list, returning the sum of the list, joining the list into a String, etc. Again, the functional programming world has a higher-order function for that, called fold.

Explaining fold in words is a little difficult. It takes three parameters (usually specified in the reverse order, but this allows me to go from "least complicated" to "most complicated"):

• A list of input values.
• A "seed" output value, which will be returned if the list input is empty.
• A function that takes the current output value and an input value and produces a new output value.

Until now, I have been describing fold as one function, but it is actually a pair of functions, foldLeft and foldRight (or foldl and foldr in Haskell). There are two reasons: one is that the binary function supplied as input may expect the output and input values in either order, and another is that there are cases (especially in Haskell, due to its lazy evaluation) where evaluating the list elements from back to front may be more efficient than evaluating them from front to back. For now, we'll just consider foldLeft. In Haskell, it has the following signature: foldl :: (b -> a-> b) -> b -> [a] -> b. In words, this says:

• Given:
  • a function that takes a b and an a (in that order), and returns a b
  • a value of type b, and
  • a list of as,
• Return a value of type b.

The simplest (and fairly common case) for fold is when the input and output types are the same. For example, we have a list of integers and want to retrieve the maximum (integer) element. In this case, we supply a function that takes two integers and returns the bigger one (or, say, the first if they're equal), and a seed value that should correspond to the "maximum of an empty list" (maybe Integer.MIN_VALUE in Java). The fold function will iterate through the list, applying the "getBigger" function (combined with the seed or previous output) and return its last output.

Without further delay, here is the foldLeft function, in a raw form, a "factory" method and a partial-application factory:

Another simple example for fold is finding the sum of a list of integers. In this case our binary operation is addition, and our seed is zero. Here is the code used to find the maximum integer in a list, find the sum of a list, build an integer from a list of digits, and concatenate the list as a comma-separated string:

Note that all of these functions are reusable. Thanks to partial application, we can hold onto a findMax function and apply it to any list of integers to get the maximum value:

Function1<Integer, List<? extends Integer>> findMax = 
        ListUtils.foldLeft(new Function2<Integer, Integer, Integer>() {
    @Override
    public Integer apply(Integer i1, Integer i2) {
        return i1 < i2 ? i2 : i1;
    }
}).apply(Integer.MIN_VALUE);

Integer max = findMax.apply(Arrays.asList(1, 2, 3, 4));

Since this will only work for integers, it's not as generally useful as one might like. It should be possible to modify it to act on List<? extends Comparable<?>>, with the caveat that the result will also be a Comparable, which then needs to be cast to the appropriate type.

Conclusions so far

Writing this and the previous post has shown me that some fairly elaborate functional programming concepts can be implemented in Java in a way that's easy enough that even I can do it, albeit with a lot of anonymous class boilerplate. I believe that Project Lambda significantly reduces this boilerplate, bringing it closer to Scala in that regard. Someday, I'll try forking my Github source for these code snippets and rewriting it against a Project Lambda build.

The main limitations I see for functional programming in standard Java so far (beyond the boilerplate) are:

• The assumption of mutability in the standard library collections is not ideal for functional programming (which, I suppose, is why the Functional Java team wrote their own immutable collections). I'll get into immutable data types and collections in a future post, where I talk about referential transparency.
• The type system in Java makes it hard to write really general, reusable higher-order functions. Maybe there are tricks I could use, but I haven't been able to figure them out (besides the raw function hack I used for map and fold). Scala's type system seems to allow more general generic (higher-kinded) types, but I find the syntax involved pretty confusing. I find Haskell the best in this regard at this point. (The dynamically-typed languages also make it easy, at the cost of compile-time type guarantees.)

Come by next time, when I'll introduce tuples, memoization, and lazy evaluation.