Currying in JS

[Twey]

I don't know how many of you are aware that ECMAScript can be used as a functional language (I suspect the definition of a functional language (http://en.wikipedia.org/wiki/Functional_programming) would probably increase that number), but I've had a fair few of people asking me on IRC how currying is accomplished in Javascript, so I thought I'd share it here in the hopes that it might reach a few of them, and maybe useful to others as well:
function curry(f /* [ , l [, a]] */) {
var l = (typeof arguments[1] === "number" ? arguments[1] : (f.length || 0)),
a = arguments[2] || [];

return function() {
var m = a.concat(Array.prototype.slice.call(arguments));
if(m.length < l)
return curry(f, l, m);
else
return f.apply(this, m);
};
}The function takes three arguments, the latter two of which are optional: the function to curry, the number of arguments to take before applying them to the function, and the arguments to store initially.

Currying allows arguments to be passed to a function one at a time, each applied argument returning either a function that can apply the next argument or a the result of the function with the given arguments, if enough arguments have been given. ECMAScript's variable arguments also allow, unusually, for a variable number of arguments to be passed to each function. For example, say we had a very simple function:
function add(a, b, c, d) {
return a + b + c + d;
}We can curry it like so:
var add6 = curry(add)(6);
add6(1, 2, 3); // returns 12 (6 + 1 + 2 + 3)
var add6and4 = add6(4);
add6and4(1, 3); // 14 (6 + 4 + 1 + 3)You can add as many arguments in each call as you like.

For a more complex example, how about a summing function that takes an arbitrary number of arguments:
function madd() {
var t = 0, i = 0;
for(; i < arguments.length; ++i)
t += arguments[i];
return t;
}We can do:
var c_madd = curry(madd);
c_madd(1);... but this returns 0 -- there are no formal parameters defined, so the function is called immediately. Attempts at further currying would, of course, fail with an error: currying a number doesn't make much sense! Instead, we can use the optional second argument:
curry(madd, 4)(1)(2)(3)(4); // 10 (1 + 2 + 3 + 4)The optional third argument is actually mostly there for internal use (it's used to pass on the current arguments for the next internal call to curry()) but it can sometimes be convenient to the user as well: curry(add, null, [1, 2, 3]) is the same as curry(add)(1, 2, 3).

Applied wisely, currying can greatly improve readability, flexibility, and code size of your scripts, since it can be used in a lot of situations where people would normally define a full-blown function.

[codeexploiter]

http://www.jibbering.com/faq/faq_notes/closures.html

[Twey]

That's for if you're reading this and had trouble understanding it, I presume. :confused:

[codeexploiter]

Not really I had bookmarked this one sometimes back and thought of providing this for other users who can continue the reading after your post a bit more. I feel that most of them addressing this as closures then currying..

[Trinithis]

Here's my latest curry code. It allows for non-sequential partial application and point-free code (extraneous arguments are propagated to result).

It will not work properly with varargs because the point-free feature would require backtracking, which has two problems:
1) JS is not referentially transparent.
2) Recursive curried functions could take non-polynomial in time. (Or at least I couldn't figure out a way to do it in polynomial time.)

Should a function have varargs, it will treat the function as if it did not have any.



Function.freeArg = {
toString: function() {
return "[object FreeArg]"
}
};

var curry = (function() {
var curryApply = function(f, context, args) {
args = Array.prototype.slice.call(args);
while(args.length > 0 && typeof f == "function")
f = f.apply(context, args.splice(0, f.length));
return f;
};

var curry = function(f /*[, arity [, initArgs]]*/) {
var initArgs = arguments[2] || [];
var arity = typeof arguments[1] == "number"
? arguments[1]
: f.length
;
return arity > 0
? function(forceArityTo1) {
if(!arguments.length)
return arguments.callee;
var A = Array.prototype;
var args = initArgs.slice();
var i;
while(i = args.indexOf(Function.freeArg, i + 1), i != -1 && arguments.length)
args[i] = A.shift.call(arguments);
A.push.apply(args, arguments);
if(args.length < arity || args.indexOf(Function.freeArg) != -1)
return curry(f, arity, args);
return curryApply(f, this, args);
}
: function() {
return curryApply(f, this, arguments);
}
;
};

return curry;
})();


Examples:


var _ = Function.freeArg;

var sub = curry(function(a, b) {
return a - b;
});

var oneMinus = sub(1);

var dec = sub(_, 1);

alert(oneMinus(5)); // -1
alert(dec(5)); // 4

//-------------------------------------------------------//

Function.prototype.o = curry(function(g) {
var f = this;
return curry(function(x) {
return f(g(x));
});
});

var foldr = curry(function(f, z, xs) {
return !xs.length
? z
: f(xs[0], foldr(f, z, xs.slice(1)))
;
});

var cons = curry(function(x, xs) {
xs = xs.slice();
xs.unshift(x);
return xs;
});

var map = curry(function(f) {
return foldr(cons. o (f), []);
});

alert(map(dec, [1, 2, 3])); // [0, 1, 2]

//-------------------------------------------------------//

// Perhaps ensureArity should be moved in the main curry module.
var ensureArity = curry(function(arity, f) {
if(arity < 1)
return function() {
return f.call(this);
};
var supplyOneArg = curry(function(accumArgs, arg) {
accumArgs = accumArgs.concat([arg]);
return accumArgs.length < arity
? supplyOneArg(accumArgs)
: f.apply(this, accumArgs)
;
});
return supplyOneArg([]);
});

var reorder = curry(function(order, f) {
return ensureArity(order.length, function() {
var args = arguments;
args = map(function(idx) {
return args[idx];
}, order);
return f.apply(this, args);
});
});

var flip = reorder([1, 0]);

alert(flip(sub, 1, 2)); // 1
alert(flip(sub)(1, 2)); // 1
alert(flip(sub, 1)(2)); // 1
alert(flip(sub)(1)(2)); // 1

[Twey]

Can you explain further about varargs requiring backtracking? I can't see how it's possible to do it with varargs at all, recalling that it's valid for a function to return a function.

[Trinithis]

Well, it would have to be with a limitation that only the last function down the apply chain (hmm I like that name more than curryApply) can have varargs.

Basically you would continually apply n arguments to the function, where n is it's arity. If the result is a function, repeat with the rest of the arguments until you run out of arguments or a non-function value is returned. In the case you run out of arguments, you're done. Otherwise, backtrack one step back to get the previous function and the old set of arguments. Now apply all the arguments to the function.

I'll give an example in Scheme:


(define (abs-arity f)
(let ((n (%procedure-arity f)))
(if (< n 0)
(abs (+ 1 n))
n)))

(define (chain-apply f args)
(define (chain-apply k f args)
(if (or (null? args)
(not (procedure? f)))
(k)
(let ((n (abs-arity f)))
(chain-apply
(lambda ()
(apply f args))
(apply f (take n args))
(drop n args)))))
(chain-apply (lambda () f) f args))


--------------------

EDIT:
Just looking at my code in the above post, I would probably move chainApply (curryApply) outside the curry closure because it's useful. Also, the inner function in the compose method does not need to be curried; the outer curry handles should handle it nicely.

Also for those who don't know better, the definition I gave for map is to demonstrate point-free code in javascript. I wouldn't recommend implementing such a trivial function in this manner, especially the cons function.