Currying and Partial Application with Java Closures

I had intended to dive straight in and continue with the earlier memoization example, extending it to work with cases where we have an arbitrary number of keys, but in writing that up I realised that I was making use of a couple of concepts which deserved a bit of explanation in their own right: currying and partial application.

There's a lot of confusion about these two, and the terms are often used interchangeably (although they are different!), partly because they naturally vary in their implementation depending on the underlying language. This blog entry is an attempt to informally describe the two concepts in a way that makes sense for Java with Closures, so that I can refer to them in later posts.

OK, first up then we have:

Currying (and uncurrying)

Say we have a function accepting 3 arguments of types A1, A2 and A3 and returning a value of type R. Its type would be:

{A1, A2, A3 => R}

This function's type in curried form would be:

{A1 => {A2 => {A3 => R}}}

Currying transforms a function which takes multiple arguments into an equivalent single-argument function which takes the first argument of the original function and returns another single-argument function, which in turn takes the second argument of the original function and returns yet another single-argument function... etc. The last single-argument function in the chain, which takes the last argument of the original function, will invoke the original function, passing all the arguments in one go, and returning its result.

If this is as clear as mud, a more concrete example may help. Imagine we have a simple 2-argument function which takes a String key and a Locale, and uses those to find a translation of some user-interface text by calling a method with the signature String lookup(String key, Locale locale) :

{String, Locale => String} translator = 
    {String key, Locale locale => lookup("somePrefix." + key, locale)};

we can use our translator function like this:

String translatedText = translator.invoke("name", customer.getLocale());

Now let's say we have a method called curry which takes any 2-argument function and returns the curried form of that function. Its signature might be:

<A1, A2, R> {A1 => {A2 => R}} curry({A1, A2 => R} fn)

This allows us to curry our translator function, and provide the arguments one at a time, rather than all in one go:

{String => {Locale => String}} curriedTranslator = curry(translator);
{Locale => String} nameTranslator = curriedTranslator.invoke("name");
String translatedText = nameTranslator.invoke(customer.getLocale());

This might not look much use at first glance, but it means that we can pass curriedTranslator to another method which knows how to provide the key but not the Locale, or that we can store nameTranslator away somewhere and use it at a later point, without having to know the key.

An implementation of the curry() method above might be:

static <A1, A2, R> {A1 => {A2 => R}} curry({A1, A2 => R} fn) {
  return {A1 a1 => {A2 a2 => fn.invoke(a1, a2)}};
}

Notice that it uses closures to capture references to the original function fn and the first argument a1 so that they are available when the final function is invoked with the value a2.

This is a slightly simplistic version of curry() - in practice we might want to pass it a function which throws one or more checked exceptions; the closures proposal has provisions for implementing this in a very nice way, and I'll cover that at a later point. More importantly, this method only curries 2-argument functions so if we want to curry a function with more arguments we'll need to write a corresponding version of the curry() method; it isn't difficult to overload curry() to cope with n arguments, but how many overloaded versions should we provide by default? Solving this particular problem for all possible values of n would probably require additional support from the language however.

In any case, the key thing to remember about currying is that it takes a multi-argument function and transforms it into an equivalent single-argument function, and this can be a very important building block for more obviously useful concepts.

It's useful to note that some functions are naturally curried - these are functions originally defined in curried form and which may actually make use of arguments before the remaining arguments have been provided. I'll provide an example of this when we get to Partial Application.


While we're at it, uncurrying is the inverse of currying - it transforms a function in curried form into one which accepts all the arguments in one go. For example, uncurrying a function whose type is of the form:

{A1 => {A2 => {A3 => R}}}

results in a function with the type:

{A1, A2, A3 => R}

A simplistic uncurry() method for 2-argument functions can be implemented as follows:

<A1, A2, R> {A1, A2 => R} uncurry({A1 => {A2 => R}} fn) {
    return {A1 a1, A2 a2 => fn.invoke(a1).invoke(a2)};
}

Partial Application

Closely related to currying is partial application. In practice, there are a number of subtly different interpretations of the term 'partial application', but let's start by informally defining it as the process of transforming a multiple-argument function into another function accepting fewer arguments, by providing some of the arguments.

For example, partially applying a function of type {A1, A2, A3 => R} to a value of type A1 results in a function of type {A2, A3 => R}. Partially applying it to two values of type A1 and A2 results in a function of type {A3 => R}.

To see this in practice, let's change the original translator example to allow different sets of translations depending on some Product:

{Product, String, Locale => String} translator = 
    {Product product, String key, Locale locale => 
        lookup(product.getName() + '.' + key,  locale)};

Now let's define a method called partial, which partially applies a 3-argument function to the value of its first argument:

<A1, A2, A3, R> {A2, A3 => R} partial({A1, A2, A3 => R} fn, A1 a1);

We can use this as follows:

{String, Locale => String} notepadTranslator = 
    partial(translator, Product.NOTEPAD);

An implementation of this version of partial() might be:

static <A1, A2, A3, R> {A2, A3 => R} partial({A1, A2, A3 => R} fn, A1 a1) {
    return {A2 a2, A3 a3 => fn.invoke(a1, a2, a3)};
}

Notice again the use of a closure to capture the meaning of fn and a1 so that they are available when a2 and a3 are finally supplied.

Interpretations in other languages often define partial application in terms of functions in curried form, which we can also do:

Partially applying a function of type {A1 => {A2 => {A3 => R}}} to a value of type A1 results in a function of type {A2 => {A3 => R}}. Partially applying it to two values of type A1 and A2 results in a function of type {A3 -> R}.

The signature for an overloaded version of partial() which works with curried functions could be:

<A1, A2, A3, R> {A2 => {A3 => R}} partial({A1 => {A2 => {A3 => R}}} fn, A1 a1);

Implementing it leads us to an interesting choice, though. We could simply define it as:

static <A1, A2, A3, R> {A2 => {A3 => R}} partial({A1 => {A2 => {A3 => R}}} fn, A1 a1) {
    return fn.invoke(a1);
}

which doesn't give us much compared to just calling fn.invoke() ourselves. Alternatively we could choose:

static <A1, A2, A3, R> {A2 => {A3 => R}} partial({A1 => {A2 => {A3 => R}}} fn, A1 a1) {
    return {A2 a2 => {A3 a3 => fn.invoke(a1).invoke(a2).invoke(a3)}};
}

with the key difference being that the second version defers any invocation until all the arguments' values have been supplied - this may sound like a subtle distinction, but if fn is a naturally curried function, there may be an observable difference. Consider the following (somewhat contrived) example which uses a fictional database connection type DBConnection to execute some SQL:

{DBConnection => {String => boolean}} dbUpdater = 
    {DBConnection conn => 
        conn.startTransaction();
        {String sql =>
            boolean success = false;
            try {
                executeUpdate(conn, sql};
                conn.commit();
                success = true;
            }
            finally {
                conn.endTransaction();
            }
            success
        }
    };

Partially applying dbUpdater with a DBConnection results in very different behaviour depending on which implementation of partial() we opt for. Using the first version, a database transaction is started immediately, but using the second this doesn't happen until the SQL is supplied, which may be at a much later point in time.

This example may not be particularly realistic, but it should illustrate the difference in behaviour between the two implementations of partial() for curried functions.

The deferring version strikes me being as the more useful of the two, as its semantics are distinct from simply invoking a curried function with each argument in turn (which is all the first version does), but I'm not certain whether this choice could prove confusing in the long run if the distinction is not fully understood.



Bear in mind that there are other interpretations of currying and partial application which will disagree with mine on various points, or extend these definitions with other variations. Hopefully the underlying ideas will be reasonably clear, although the trivial examples above will probably seem less than convincing right now - the memoization follow-up will make better use of them.

I also have a rapidly growing set of implementations of curry, uncurry, partial and other useful methods which I'll try to include.