Currying and Abstraction over Arity

Type-directed Functional Programming for Non-Mathematicians in Javascript

Preamble

This is a series of loosely connected posts around type-directed functional programming in Javascript. You can use ftor - a pluggable runtime type checker - to reproduce the code given in this post in a virtually typed Javascript environment.

Definition

Currying is a technique that refers to function declarations. In its original mathematical sense it is the transformation of a function with n parameters into a sequence of n functions, which each return an unary, anonymous function. More precisely, the arity is transformed from n-ary to n * 1-ary. But why limit it to one argument? Because it allows us to simplify the functional interface considerably. And because this limitation entails very desirable properties, as we’ll hopefully see in the course of this post.

const add = x => y => x + y; // curried function declaration

add(1) (2); // procedural application
const inc = add(1); // partial application

Currying is right-associative, that is to sayadd = x => y => x + y is equivalent to add = x => (y => x + y). By partially applying curried functions, we can defer the execution of the actual computation over which they abstract. Moreover, the resulting intermediate anonymous functions (lambdas) are often very useful themselves.

Delimitation to Partial Application

Currying has its own notion of partial application, namely partially applying a function sequence. This notion is regularly confused with partial application of multi-argument functions:

const partial = (f, ...xs) => (...ys) => f(...xs, ...ys);

const reduce = (f, acc, xs) => xs.reduce(f, acc);

const add = (x, y) => x + y;

const sum = partial(reduce, add, 0);

sum([1, 2, 3, 4]) // 10

A partially applied multi-argument function has received some but not all of its required arguments and waits to receive the pending ones with the next invocation.

Why Curry

It’s difficult to illustrate the benefit of currying, because the concept acts systemic. Systemic means that a property needs to interact with other basic properties in order to fully develop its advantages. There is a mutual dependency between the properties involved.

One of these concepts currying is playing nicely with are higher order functions, which themselves derive from first class functions. Currying makes working with higher order functions much more effective, provided the passed in functions are in curried form themselves. Since higher order functions are such an important concept and ubiquitous in the functional paradigm, this interaction can be considered the killer application of currying.

The most significant advantage of currying along with higher order functions is abstraction over arity. Whenever a higher order function is polymorphic in its return value, the passed function argument can be of arbitrary arity. The following compostion operator, which composes two unary functions, illustrates the concept quite nicely:

const comp = f => g => x => f(g(x));

const inc = x => x + 1; // unary function
const mul = y => x => x * y; // binary function
// normal composition of two unary functions
comp(inc) (inc) (2); // 4
// composition of a binary and an unary function
comp(mul) (inc) (2) (3); // 9
// invalid composition of an inner binary function
comp(inc) (mul) (2) (3); // type error

As you can see from the type error, abstraction over arity doesn’t always work. The involved types must be compatible. The underlying mechanism becomes more obvious when we take a closer look at the type level:

comp :: (b -> c) -> (a -> b) ->  a -> c      
         f       =>  g       => (x => f(g(x)))

f‘s arity doesn’t matter, because comp is polymorphic in its return type c. If f is substituted withinc, comp‘s return type becomes x => f(g(x)). If f is substituted with mul, comp‘s return type becomes x => y => f(g(x)) (y), which is perfectly valid. However, this doesn’t apply to g, hence the type error above.

As already mentioned, another benefit of currying is that partially applied functions are often useful themselves, because they allow you to derive functionality without having to declare a separate function each time. This applies not only to simple cases such as deriving inc from a partial applied add, but also for far more complex examples.

How to Curry

Functions in your own realm

The concise arrow syntax that ships with EcmaScript 2015 makes it a piece of cake to declare manually curried functions with little syntactic overhead:

const add = m => n => m + n;
// ES5...
function add(m) {
  return function(n) {
    return m + n;
  };
}

Third party functions

Multi-argument functions beyond your control can be programmatically curried with a corresponding combinator:

const add = (m, n) => m + n;
const curry = f => x => y => f(x, y);
const curry3 = f => x => y => z => f(x, y, z);
const curriedAdd = curry(add); // programmatic currying
curriedAdd(2) (3); // 5

Methods

Instead of going through the trouble of programmatically currying methods just use simple wrappers:

const reduce = f => acc => xs =>
  xs.reduce((acc_, x) => f(acc_) (x), acc);

Uncurry

Sometimes what you really want is to uncurry a function in order to gain compatibility to native ones:

const uncurry = f => (x, y) => f(x) (y);
const uncurry3 = f => (x, y, z) => f(x) (y) (z);
const add = m => n => m + n;
const xs = [1, 2, 3, 4];
xs.reduce(uncurry(add), 0); // 10

Variadic functions

Variadic functions except any number of arguments and are thus incompatible with currying. You can certainly define variadic functions in curried form by supplying an explicit length argument, but this is merely a nice hack, as both concepts contradict each other. My advice is to not waste your time on this.

Optional Arguments

While I must admit that variadic functions are sometime convenient, I really dislike functions containing optional arguments. Currying is a concept to avoid just that. If your curried functions really need optional arguments, rather use a configuration object.

Optional arguments obscure the mathematical origin of functions and complicate their interface, without giving you much.

Why Argument Order Matters

Abstractions are always a trade-off and so is currying. Since we supply only one argument per call, their order gains more importance:

const sub = m => n => m - n;
const sub_ n => m => m - n;
const dec = sub(1);
const dec_ = sub_(1);
sub(10) (5); // 5 (A)
sub_(10) (5); // -5 (B)
dec(10); // -9 (C)
dec_(10); // 9 (D)

We can probably agree on that the application in line C is certainly counterintuitive . But the other examples tempt to be interpreted differently. Some people will read line A “subtract 10 from 5”, others as “subtract 5 from 10”. The proper solution for this ambiguity would be to apply functions in infix position as we do with operators. This isn’t valid Javascript, though:

(10) sub (5) // syntax error

There is no simple solution to this issue in Javascript. You must decide for yourself which style to use and than stick to it. Here are some combinators to ease the pain:

const $ = (x, f, y) => f(x) (y);
const _ = f => y => x => f(x) (y); // aka flip
const sub = m => n => m - n;
const dec = _(sub) (1);
dec(10); // 9
$(10, sub, 5); // 5

I’ve used syntactic names rather than semantic ones in order to imply that this combinators are actually operators. The expression _(sub) (1) indicates visually that sub is applied to its second argument, whereas the first argument on the left side is pending.

Please note that the argument order only concerns non-commutative functions:

add(2) (3) === add(3) (2); // commutative
sub(2) (3) !== sub(3) (2); // non-commutative

When you compare the parameter order of curried with multi-argument functions at declaration time, two essential rules arise for curried functions:

• the primary parameter should be placed at the end to facilitate function composition
• parameters that are least likely to change should be placed leftmost to facilitate partially applied functions

Don’t!

You ought not

• relay on Function’s length property
• use magic auto currying, that is functions as return values are curried automatically
• use programmatic curry solutions that allow partial application in arbitrary positions of the argument list (e.g. reduce(f, __, xs))