Currying

Currying #

Illustration #

Example (continued).

In the previous section, we encountered the function $g \colon \mathbb{N} \to (\mathbb{N} \to \mathbb{N})$ defined by:

$$ g(x) = y \mapsto x^y$$

As we saw in a previous exercise, for any pair $(x,y) \in \mathbb{N} \times \mathbb{N}$: $$ g(x)(y) = x^y $$

The function $g$ is called the curried form of the function

$$(x, y) \mapsto x^y $$

Notation #

Before defining currying, we introduce a convenient notation:

Syntax. By default, the $\mapsto$ symbol (used to define a function anonymously) and the $\to$ symbol (used to specify the type of a function) associate to the right.

Examples.

The anonymous function $$ x \mapsto (y \mapsto x + y) $$ can be written $$ x \mapsto y \mapsto x + y $$

Similarly, the type

$\qquad \qquad$ City $\to$ (Integer $\to$ City)

can be written

$\qquad \qquad$ City $\to$ Integer $\to$ City

Definition #

Definition. If $f$ is a function with $n$ arguments, then $f$ in curried form is the function

$$ x_1 \mapsto .. \mapsto x_n \mapsto f(x_1, .., x_n) $$

If $f$ has type $$T_1 \times .. \times T_n \to T_{\text{output}}$$

then its curried form has type $$T_1 \to .. \to T_n \to T_{\text{output}}$$

Example. If $f$ takes 3 arguments, and if $g$ is $f$ in curried form, then $$ f(x_1, x_2, x_3) = g(x_1)(x_2)(x_3)$$

Usage #

Currying is central to most functional programming languages. For instance, functions in Haskell are traditionally written in curried form.

Code factorization #

Example.

In Java, we may have a method with signature

void convert(int radix, int input)

that prints the digits of the number input in base radix (for instance, convert(2,5) should print 101).

We may want to do this for each element of a list of numbers myList, and for different bases, e.g. once in base 2 and once in base 8.

We could declare two new methods:

void convertToBaseTwo(int input){
    convert(2, input);
}

void convertToBaseEight(int input){
    convert(8, input);
}

Then we could pass these two methods to the method forEach encountered earlier:

myList.forEach(MyClass::convertToBaseTwo);
myList.forEach(MyClass::convertToBaseEight);

However, with this pattern, for each new radix X, we would need to create a new method convertToBaseX. Besides, if the desired radix is only supplied at runtime (e.g. by the system’s user), then this pattern cannot be applied.

Intuitively, we would like to produce (on the fly) a method convertToBaseX that converts an integer into base X. This is precisely what the curried form of the method convert does.

This method has type Integer $\to$ Integer $\to$ void, and can be defined as:

Consumer<Integer> curriedConvert(int radix) {
    return x -> convert(radix, x);
}

This allows us to generate closures and pass them as arguments to the method forEach:

myList.forEach(curriedConvert(2));
myList.forEach(curriedConvert(8));

int radix = getRadixFromUser();
myList.forEach(curriedConvert(radix));

Alternatively, we could use the curried form of convert anonymously:

myList.forEach(x -> convert(2, x));
myList.forEach(x -> convert(8, x));

int radix = getRadixFromUser();
myList.forEach(x -> convert(radix, x));

N-ary method #

We saw earlier that Java has native types (precisely, functional interfaces) for methods with up to two arguments. For instance Function and BiFunction, Consumer and BiConsumer, Supplier, etc.

However, there is no such type for methods with more than two arguments. One workaround (among others) consists in using curried methods.

Example. Assume that we want to write a method that takes as input a callback method with type

$\qquad$ Integer $\times$ Integer $\times$ Integer $\to$ String

There is no native type in Java for the callback method.

Instead, we can use a callback method in curried form, with type

$\qquad$ Integer $\to$ Integer $\to$ Integer $\to$ String

Or in Java

Function<Integer, Function<Integer, Function<Integer, String>>>