The Many Ways
Currying
Named after Haskell Brooks Curry, currying is breaking down a function into a series of functions that each a single argument.
Currying example
Here’s a simple example. We’ll write a function sum3 takes three numbers and returns their sum.
function sum3(x, y, z) {
return x + y + z;
}
console.log(sum3(1, 2, 3) // 6
The curried version of sum3 behaves a little differently.
For starters, it accepts only one argument and returns a function. The returned function also accepts one argument and also returns a function.
This cycle keeps going until the returned function is the one accepting the last argument. This function, the last one in the chain, finally returns the sum.
function sum3(x) {
return (y) => {
return (z) => {
return x + y + z;
};
};
}
console.log(sum3(1)(2)(3)) // 6
This works because JS supports closures. What’s a closure?
A closure is the combination of a function and the lexical environment within which that function was declared. — MDN
Observer that the last function in the chain only accepts z, but operates on other variables. For all it cares, they are global variables. When in reality, they’re just scoped variables of different functions.
let x = ...;
let y = ...;
return function(z) {
return x + y + z;
};
Generalised curry
Writing one curried function is all fine and dandy, but this becomes a real challenge when writing multiple methods. We need a more general solution.
In most functional languages, like haskell, all we have to do is define the function and it gets curried automagically.
let sum3 x y z = x + y + z
sum3 1 2 3
-- 6
:t sum3 -- print the type of sum3()
-- sum3 :: Int -> Int -> Int -> Int
sum3 :: Int -> Int -> Int -> Int -- function name
sum3 :: Int -> Int -> Int -> Int -- curried function definition
sum3 :: Int -> Int -> Int -> Int -- final return
We can’t write the JS engine to currify all functions, but we can come up with a strategy to do so.
The Strategy
Examining the two forms of sum3 reveals an important fact. The actual function body from the plain function gets transferred as-is to the last function in the chain.
function sum3(x, y, z) {
//...
}
function sum3(x) {
return (y) => {
return (z) => {
// ...
};
};
}
Before we reach the last level, we won’t have all the arguments in the execution scope. This means that we create a wrapper function that collects the arguments and calls the real function. All the intermediate nested functions are called accumulator functions — at least that’s what I call them.
function _sum3(x, y, z) {
return x + y + z;
}
function sum3(x) {
return (y) => {
return (z) => {
return _sum3(x, y, z);
};
};
}
sum3(1)(2)(3) // 6 <-- It works!
Curry Wrapper
Since we’re using a wrapper function in place of the real function, we can create another function that generates this wrapper function. We’ll call this new function curry — a higher-order function.
function curry(fn) {
return (x) => {
return (y) => {
return (z) => {
return fn(x, y, z);
};
};
};
}
const sum3 = curry((x, y, z) => {
return x + y + z;
});
sum3(1)(2)(3) // 6 <-- It works!
All we now need are different arity curry functions that take: 0 arguments, 1 argument, 2 arguments and so on — not really.
Recursive Curry
Instead of writing multiple wrapper functions, we will write a curry function such that it works for functions of all arity.
Let’s say we do write multiple curry functions. This is what they’ll look like:
function curry0(fn) {
return fn();
}
function curry1(fn) {
return (a1) => {
return fn(a1);
};
}
function curry2(fn) {
return (a1) => {
return (a2) => {
return fn(a1, a2);
};
};
}
function curry3(fn) {
return (a1) => {
return (a2) => {
return (a3) => {
return fn(a1, a2, a3);
};
};
};
}
...
function curryN(fn){
return (a1) => {
return (a2) => {
...
return (aN) => {
// N-th nested function
return fn(a1, a2, ... aN);
};
};
};
}
We can make a few observations:
- The i-th accumulator returns another function that is the (i+1)-th accumulator. We can also say that it is the j-th accumulator.
- The i-th accumulator accepts the i-th argument, while maintaining the previous i - 1 arguments in its environment.
- There will be N nested functions, where N is the arity of function fn.
- The N-th function always calls and returns fn.
- curry0 is pointless waste of a function and should not exist.
Using the above observations, we can see that the curry function returns a nested structure of self-similar accumulator functions. We can easily generate such a structure using recursion.
function nest(fn) {
return (x) => {
// accumulator function
};
}
function curry(fn) {
return nest(fn);
}
We obviously need a terminal case else our code will form an infinite fractal. We will maintain a variable i that keeps track of our current level. The terminal case will be when i === N.
function nest(fn, i) {
return (x) => {
if (i === fn.length) {
return fn();
}
return nest(fn, i + 1);
};
}
function curry(fn) {
return nest(fn, 1);
}
Next up, we need to store the accumulated arguments and pass them to fn() in the terminal case. The easiest solution is to create an array args inside curry and pass it to nest.
function nest(fn, i, args) {
return (x) => {
args.push(x);
if (i === fn.length) {
return fn(...args);
}
return nest(fn, i + 1, args);
};
}
function curry(fn) {
const args = [];
return nest(fn, 1, args);
}
Just add a guard for 0-arity functions and we are done.
function curry(fn) {
if (fn.length === 0) {
return fn;
}
const args = [];
return nest(fn, 1, args);
}
It’s a good idea to test our code at this stage:
const log1 = curry((x) => console.log(x));
log1(10); // 10
const log2 = curry((x, y) => console.log(x, y));
log2(10)(20); // 10 20
You can run your tests here on codepen.
Tweaks and Optimisations
At this point, we can either do nothing or we can try to optimise our code.
For starters, we can move nest inside curry, thus reducing the number of arguments passed to nest by reading fn and args from the closure.
function curry(fn) {
if (fn.length === 0) {
return fn;
}
const args = [];
function nest(i) {
return (x) => {
args.push(x);
if (i === fn.length) {
return fn(...args);
}
return nest(i + 1);
};
}
return nest(1);
}
Let’s tweak this new curry to be more functional and not rely on closure variables. We do this by supplying args and fn.length as nest arguments.
Further still, instead of passing fn.length for comparison, we can pass the remaining depth of recursion.
function curry(fn) {
if (fn.length === 0) {
return fn;
}
function nest(N, args) {
return (x) => {
if (N - 1 === 0) {
return fn(...args, x);
}
return nest(N - 1, [...args, x]);
};
}
return nest(fn.length, []);
}
Variadic Curry
Let’s see our old friend sum3 and its older brother sum5:
const sum3 = curry((x, y, z) => {
return x + y + z;
});
const sum5 = curry((a, b, c, d, e) => {
return a + b + c + d + e;
});
sum3(1)(2)(3) // 6 <-- It works!
sum5(1)(2)(3)(4)(5) // 15 <-- It works!
Look at this abomination of a code! No doubt it works, but it looks …
In haskell and other functional languages, the syntax is pretty relaxed. Compared to this monstrosity, let’s see how haskell deals with it:
let sum3 x y z = x + y + z
let sum5 a b c d e = a + b + c + d + e
sum3 1 2 3
> 6
sum5 1 2 3 4 5
> 15
sum5 1 2 3 (sum3 1 2 3) 5
> 17
If you ask me, even the simple function calls in JS look better:
sum5(1, 2, 3, 4, 5) // 15
But this doesn’t mean we have to give up on currying. What we can do is settle for some middle ground. A system where the curried, the uncurried syntaxes both work and the ones in between work too.
sum3(1, 2, 3)
sum3(1, 2)(3)
sum3(1)(2, 3)
sum3(1)(2)(3)
We need a simple modification — convert accumulators to variadic functions.
However, when the i-th accumulator accepts k arguments, the next accumulator won’t be of N - 1 depth, but rather N - k depth. We were using N - 1 because all accumulators were accepting one argument each.
This also means that we no longer require the 0-arity guard.
function curry(fn) {
function nest(N, args) {
return (...xs) => {
if (N - xs.length === 0) {
return fn(...args, ...xs);
}
return nest(N - xs.length, [...args, ...xs]);
};
}
return nest(fn.length, []);
}
It’s testing time. You can run your tests here on codepen.
function curry(){...}
const sum3 = curry((x, y, z) => x + y + z);
console.log(
sum3(1, 2, 3),
sum3(1, 2)(3),
sum3(1)(2, 3),
sum3(1)(2)(3),
);
// 6 6 6 6
It works!
Bonus
We did it! We created a curry function that takes multi-arity functions and returns variadic curried function(s). This would be a good time to take a bow.
There is yet another method of currying in JS.
In JS, we can bind arguments to a function and create a bound copy of it. The resultant function is said to be “partially applied” — partially, because the function already holds some of its arguments, but requires some more before invocation.
Up until now, curry would return a function that accumulates arguments until all arguments were received and then invoke fn with the arguments. By binding arguments to the function, we can remove the need for multiple nested accumulator functions.
And this is what we get:
function curry(fn) {
return (...xs) => {
if (xs.length >= fn.length) {
return fn(...xs);
}
return curry(fn.bind(null, ...xs));
};
}
Here’s how it works. curry takes an N-arity function and returns an accumulator function. When the accumulator is invoked with k number of arguments, we check if k >= N, i.e. whether or not the function’s arity is satisfied.
If it is, we invoke fn with the arguments. If not, we create a copy of fn that has k arguments partially applied and pass it to curry as the next fn, with its reduced arity of N - k.
The End
We covered the generic approach to currying by using nested accumulators. This approach will work in any language that supports first-class functions. We saw the difference between strict currying and variadic currying. We also saw how easy things got in JS, thanks to the bind method.
If you’re interested in the source code, you’d have to head over to codepen.