How to correctly curry a function in JavaScript?
@Aadit,
I'm posting this because you shared a comment on my answer to To “combine” functions in javascript in a functional way? I didn't specifically cover currying in that post because it's a very contentious topic and not really a can of worms I wanted to open there.
I'd be wary using the phrasing "how to correctly curry" when you seem to be adding your own sugar and conveniences into your implementation.
Anyway, all of that aside, I truly don't intend for this to be an argumentative/combative post. I'd like to be able to have an open, friendly discussion about currying in JavaScript while emphasizing some of the differences between our approaches.
Without further ado...
To clarify:
Given f
is a function and f.length
is n
. Let curry(f)
be g
. We call g
with m
arguments. What should happen? You say:
- If
m === 0
then just returng
.- If
m < n
then partially applyf
to them
new arguments, and return a new curried function which accepts the remainingn - m
arguments.- If
m === n
then applyf
to them
arguments. If the result is a function then curry the result. Finally, return the result.- If
m > n
then applyf
to the firstn
arguments. If the result is a function then curry the result. Finally, apply the result to the remainingm - n
arguments and return the new result.
Let's see a code example of what @Aadit M Shah's code actually does
var add = curry(function(x, y) {
return function(a, b) {
return x + y + a + b;
}
});
var z = add(1, 2, 3);
console.log(z(4)); // 10
There are two things happening here:
- You're attempting to support calling curried functions with variadic arguments.
- You're automatically currying returned functions
I don't believe there's a lot of room for debate here, but people seem to miss what currying actually is
via: Wikipedia
In mathematics and computer science, currying is the technique of translating the evaluation of a function that takes multiple arguments (or a tuple of arguments) into evaluating a sequence of functions, each with a single argument...
I'm bolding that last bit, because it's so important; each function in the sequence only takes a single argument; not variadic (0, 1, or more) arguments like you suggest.
You mention haskell in your post, too, so I assume you know that Haskell has no such thing as functions that take more than one argument. (Note: a function that takes a tuple is still just a function that takes one argument, a single tuple). The reasons for this are profound and afford you a flexibility in expressiveness not afforded to you by functions with variadic arguments.
So let's re-ask that original question: What should happen?
Well, it's simple when each function only accepts 1 argument. At any time, if more than 1 argument is given, they're just dropped.
function id(x) {
return x;
}
What happens when we call id(1,2,3,4)
? Of course we only get the 1
back and 2,3,4
are completely disregarded. This is:
- how JavaScript works
- how Wikipedia says currying should work
- how we should implement our own
curry
solution
Before we go further, I'm going to use ES6-style arrow functions but I will also include the ES5 equivalent at the bottom of this post. (Probably later tonight.)
another currying technique
In this approach, we write a curry function that continuously returns single-parameter functions until all arguments have been specified
As a result of this implementation we have 6 multi-purpose functions.
// no nonsense curry
const curry = f => {
const aux = (n, xs) =>
n === 0 ? f (...xs) : x => aux (n - 1, [...xs, x])
return aux (f.length, [])
}
// demo
let sum3 = curry(function(x,y,z) {
return x + y + z;
});
console.log (sum3 (3) (5) (-1)); // 7
OK, so we've seen a curry
technique that is implemented using a simple auxiliary loop. It has no dependencies and a declarative definition that is under 5 lines of code. It allows functions to be partially applied, 1 argument at a time, just as a curried function is supposed to work.
No magic, no unforeseen auto-currying, no other unforeseen consequences.
But what really is the point of currying anyway?
Well, as it turns out, I don't really curry
functions that I write. As you can see below, I generally define all of my reusable functions in curried form. So really, you only need curry
when you want to interface with some functions that you don't have control over, perhaps coming from a lib or something; some of which might have variadic interfaces!
I present curryN
// the more versatile, curryN
const curryN = n => f => {
const aux = (n, xs) =>
n === 0 ? f (...xs) : x => aux (n - 1, [...xs, x])
return aux (n, [])
};
// curry derived from curryN
const curry = f => curryN (f.length) (f);
// some caveman function
let sumN = function() {
return [].slice.call(arguments).reduce(function(a, b) {
return a + b;
});
};
// curry a fixed number of arguments
let g = curryN (5) (sumN);
console.log (g (1) (2) (3) (4) (5)); // 15
To curry or not to curry? That is the question
We'll write some examples where our functions are all in curried form. Functions will be kept extremely simple. Each with 1
parameter, and each with a single return expression.
// composing two functions
const comp = f => g => x => f (g (x))
const mod = y => x => x % y
const eq = y => x => x === y
const odd = comp (eq (1)) (mod (2))
console.log (odd(1)) // true
console.log (odd(2)) // false
Your countWhere
function
// comp :: (b -> c) -> (a -> b) -> (a -> c)
const comp = f => g => x =>
f(g(x))
// mod :: Int -> Int -> Int
const mod = x => y =>
y % x
// type Comparable = Number | String
// eq :: Comparable -> Comparable -> Boolean
const eq = x => y =>
y === x
// odd :: Int -> Boolean
const odd =
comp (eq(1)) (mod(2))
// reduce :: (b -> a -> b) -> b -> ([a]) -> b
const reduce = f => y => ([x,...xs]) =>
x === undefined ? y : reduce (f) (f(y)(x)) (xs)
// filter :: (a -> Boolean) -> [a] -> [a]
const filter = f =>
reduce (acc => x => f (x) ? [...acc,x] : acc) ([])
// length :: [a] -> Int
const length = x =>
x.length
// countWhere :: (a -> Boolean) -> [a] -> Int
const countWhere = f =>
comp (length) (filter(f));
console.log (countWhere (odd) ([1,2,3,4,5]))
// 3
Remarks
So to curry or not to curry?
// to curry
const add3 = curry((a, b, c) =>
a + b + c
)
// not to curry
const add3 = a => b => c =>
a + b + c
With ES6 arrow functions being the go-to choice for today's JavaScripter, I think the choice to manually curry your functions is a no-brainer. It's actually shorter and has less overhead to just write it out in curried form.
That said, you're still going to be interfacing with libs that do not offer curried forms of the functions they expose. For this situation, I'd recommend
curry
andcurryN
(defined above)partial
(as defined here)
@Iven,
Your curryN
implementation is very nice. This section exists solely for you.
const U = f=> f (f)
const Y = U (h=> f=> f(x=> h (h) (f) (x)))
const curryN = Y (h=> xs=> n=> f=>
n === 0 ? f(...xs) : x=> h ([...xs, x]) (n-1) (f)
) ([])
const curry = f=> curryN (f.length) (f)
const add3 = curry ((x,y,z)=> x + y + z)
console .log (add3 (3) (6) (9))
The problem with your curry
function (and for most curry
functions that people write in JavaScript) is that it doesn't handle extra arguments correctly.
What curry
does
Suppose f
is a function and f.length
is n
. Let curry(f)
be g
. We call g
with m
arguments. What should happen?
- If
m === 0
then just returng
. - If
m < n
then partially applyf
to them
new arguments, and return a new curried function which accepts the remainingn - m
arguments. - Otherwise apply
f
to them
arguments and return the result.
This is what most curry
functions do, and this is wrong. The first two cases are right, but the third case is wrong. Instead, it should be:
- If
m === 0
then just returng
. - If
m < n
then partially applyf
to them
new arguments, and return a new curried function which accepts the remainingn - m
arguments. - If
m === n
then applyf
to them
arguments. If the result is a function thencurry
the result. Finally, return the result. - If
m > n
then applyf
to the firstn
arguments. If the result is a function thencurry
the result. Finally, apply the result to the remainingm - n
arguments and return the new result.
The problem with most curry
functions
Consider the following code:
const countWhere = compose(compose(length), filter);
countWhere(odd, [1,2,3,4,5]);
If we use the incorrect curry
functions, then this is equivalent to:
compose(compose(length), filter, odd, [1,2,3,4,5]);
However, compose
only accepts three arguments. The last argument is dropped:
const compose = curry((f, g, x) =>f(g(x)));
Hence, the above expression evaluates to:
compose(length)(filter(odd));
This further evaluates to:
compose(length, filter(odd));
The compose
function expects one more argument which is why it returns a function instead of returning 3
. To get the correct output you need to write:
countWhere(odd)([1,2,3,4,5]);
This is the reason why most curry
functions are wrong.
The solution using the correct curry
function
Consider the following code again:
const countWhere = compose(compose(length), filter);
countWhere(odd, [1,2,3,4,5]);
If we use the correct curry
function, then this is equivalent to:
compose(compose(length), filter, odd)([1,2,3,4,5]);
Which evaluates to:
compose(length)(filter(odd))([1,2,3,4,5]);
Which further evaluates to (skipping an intermediate step):
compose(length, filter(odd), [1,2,3,4,5]);
Which results in:
length(filter(odd, [1,2,3,4,5]));
Producing the correct result 3
.
The implementation of the correct curry
function
Implementing the correct curry
function in ES6 is straightforward:
const curried = Symbol("curried");
Object.defineProperty(curry, curried, { value: true });
function curry(functor, ...initArgs) {
if (arguments.length === 0) return curry;
if (typeof functor !== "function") {
const value = JSON.stringify(functor);
throw new TypeError(`${value} is not a function`);
}
if (functor[curried]) return functor(...initArgs);
const arity = functor.length;
const args = initArgs.length;
if (args >= arity) {
const result = functor(...initArgs.slice(0, arity));
return typeof result === "function" || args > arity ?
curry(result, ...initArgs.slice(arity)) : result;
}
const result = (...restArgs) => curry(functor, ...initArgs, ...restArgs);
return Object.defineProperty(result, curried, { value: true });
}
I am not sure how fast this implementation of curry
is. Perhaps somebody could make it faster.
Implications of using the correct curry
function
Using the correct curry
function allows you to directly translate Haskell code into JavaScript. For example:
const id = curry(a => a);
const flip = curry((f, x, y) => f(y, x));
The id
function is useful because it allows you to partially apply a non-curried function easily:
const add = (a, b) => a + b;
const add2 = id(add, 2);
The flip
function is useful because it allows you to easily create right sections in JavaScript:
const sub = (a, b) => a - b;
const sub2 = flip(sub, 2); // equivalent to (x - 2)
It also means that you don't need hacks like this extended compose
function:
What's a Good Name for this extended `compose` function?
You can simply write:
const project = compose(map, pick);
As mentioned in the question, if you want to compose length
and filter
then you use the (f .) . g
pattern:
What does (f .) . g mean in Haskell?
Another solution is to create higher order compose
functions:
const compose2 = compose(compose, compose);
const countWhere = compose2(length, fitler);
This is all possible because of the correct implementation of the curry
function.
Extra food for thought
I usually use the following chain
function when I want to compose a chain of functions:
const chain = compose((a, x) => {
var length = a.length;
while (length > 0) x = a[--length](x);
return x;
});
This allows you to write code like:
const inc = add(1);
const foo = chain([map(inc), filter(odd), take(5)]);
foo([1,2,3,4,5,6,7,8,9,10]); // [2,4,6]
Which is equivalent to the following Haskell code:
let foo = map (+1) . filter odd . take 5
foo [1,2,3,4,5,6,7,8,9,10]
It also allows you to write code like:
chain([map(inc), filter(odd), take(5)], [1,2,3,4,5,6,7,8,9,10]); // [2,4,6]
Which is equivalent to the following Haskell code:
map (+1) . filter odd . take 5 $ [1,2,3,4,5,6,7,8,9,10]
Hope that helps.