On this page, we'll look into what currying means, and just how to go about doing this in JavaScript. If you are fully on top of what currying means, you can skip right to the JavaScript section. To examine what currying means, I will use the language SML (often referred to as "ML"), the implementation I use is Moscow ML, but it shouldn't matter. It's not necessary, to download the program, to do anything, I will explain matters as we go along.
You need to know what currying means, if you're going to be bothered to read all this. Currying is a useful technique, with which you can partially evaluate functions. What does this mean? Lets give an example.
Lets say we have a function myFunc, it takes two arguments,
and adds these. I will now show some JavaScript, but not
give the code to myFunc (that'll come later).
This is just so you can get an idea, what it does.
alert(myFunc(2,2)); // alerts 4
var adds4 = myFunc(4); // adds4, is now a function,
// which adds 4, to it's argument.
alert(adds4(5)); // alerts 9.
It's the second line, which is the key. If you give a curried function,
less arguments, then it expects, it will give you back, a function, which
has been fed the arguments you gave it, and will accept the remaining ones.
In the example above, we first gave it 4 (myFunc(4)), and
it was waiting for another number, and we gave it 9.
You need to learn a little about this language, to understand the code that will follow. It will be ultra brief, and tailored to this lesson I promise ;)
ML is type strict, unlike JavaScript. Which is one of the reasons I choose this language, to showcase the principle of currying. JavaScript being typeless, is also one of the reasons, why it cannot curry functions by itself, we need to do it for it.
ML is a functional language, and in many ways, looks and works a lot like JavaScript. Functions are of course a data type.
When entering stuff, into the ML interpreter, the line is preceded by a hyphen "-", what ML spits back at you (errors, results, etc), are preceded by greater-then sign ">". Now, lets look at some of the "signs", that ML uses, and I will explain each part in turn. After entering a command, you use the ";" to indicate you are done, and that ML can start evaluating your program.
- 2; > val it = 2 : int
Here, I simply wrote "2;", and pressed enter. The line following, is
what ML says back. The left side of the colon ":", is the actual result,
the right side, is the type of this result. In this case, it says
int, indicating that the result is an int. The "val", is the
statement you use, for variables in ML (value), it's analog to JavaScript's,
"var" statement. Now, what is this "it = 2"? Obviously,
it's some variable, called it, which is equal to 2. Now what's
it? it is the variable, into which, ML puts the
most recent result if the result was not saved in a variable.
An example should show things clearly (my comments are added to the end of
each line, they are not from the program!):
- it + 2; // take the it variable, add 2. > val it = 4 : int // it now has value 4 - val myVar = it + 2; // again, take it, add 2, but save result in myVar > val myVar = 6 : int // it still has value 4, but myVar has value 6 - myVar + 2; // take myVar, add 2 > val it = 8 : int // it has now been erased again, has value 8
Note how I use the variable it, and add to it, and also note
how I declare a variable myVar, which can now be used as I want.
It's important to see, that it is erased each time a result is
not saved.
Now you know about the basics in declaring variables, lets look at functions. Lets start with a function, which takes one input, and returns this, plus 1. It looks like this:
- fun add1 x = x + 1; > val add1 = fn : int -> int
Now, this looks a bit more complicated. fun is the function
declaration, add1 is the function name, x
is the one argument the function takes. = indicates the
start of the function body. x + 1 is the actual body,
and also what is returned (that it's returned is implied, ML
has no return statement, like JavaScript).
What ML says back is very interesting. val indicates that
this is a value, which is what we expects, as ML has functions as a
datatype. Now, a variable called add1, which has the type,
fn : int -> int. This means, that it is a function (the
fn thing), and that it goes from int, to int. That is, it
expects one argument, of type int, and it will return an int.
Lets look at one usage of this function, and then move on to
some deeper theory.
- add1 3; > val it = 4 : int // just as we expect - val myResult = add1 3; > val myResult = 4 : int // nothing surprising
Now, we move on, to the concept of an anonymous function. A function, which has no name. Contrary to what you might think, it's a very useful concept.
In order to create an anonymous function, it's much like simply
writing "3", at a prompt, and seeing what comes back.
Let's do this:
- fn x => x + 2; > val it = fn : int -> int
We denote, that this is a function, by writing "fn", and
stating the one argument, that the function expects ("x").
This then goes over into (=>), a function body which
says x + 2. We also see our old friend it,
which now is a function (we examined the function signature, in the
last section).
But instead of having to write it over and over again, we can give the anonymous function a name. The parenthesis are purely cosmetic.
- val add2 = (fn x => x + 2); > val add2 = fn : int -> int
Well, this might be all fine, but what on earth, does this have to do with currying? We've just got to that section. Let's examine a function, which takes two arguments.
fun add x y = y + x
Now, how does this translate, into the long form? We might try this:
fn x y => x + y;
But that won't work (ML complains). The problem is that anonymous functions, can only have one argument!. Now, how do we solve this argument? Simple, like this:
val add = (fn x => (fn y => x + y));
The parenthesis are again cosmetic. We see, that if we just pass one
argument, to the function, it will get replaced, by the right side, of the
=>, in the outermost function. If we pass it both, at once,
both parenthesis are evaluated, and a number is given. Lets see what happens,
as the code runs.
add 2 3 // what you enter on a line.
(fn x => (fn y => x + y)) add 2 3 // substitution off variables,
// in this case add
(fn y => 2 + y) 3 // substitution, of x with 2,
// in the outer parenthesis' body
2 + 3 // substitution, of y with 3,
// in the inner parenthesis' body
5 // computation
We are now ready, to see at this function, in ML, and what ML has to say about it.
- val add = (fn x => (fn y => x + y)); > val add = fn : int -> int -> int
We clearly see, how the -> arrows indicate flow.
add is a function, which expects one integer, and returns a function,
which expects one integer, and returns a integer.
- add 2 3; > val it = 5 : int - add 2; > val it = fn : int -> int
All as expected. So, there you have it, partially evaluated functions. If you want the full lowdown on the theory behinds this (who doesn't!), you will have to read about Lambda functions. Here is a fine tutorial on the subject. We now move on to show how this is best done in JavaScript.
You've now seen (or at the very least, glimpsed at) the theory, behind the principles. Now, let's see how we best do this in JavaScript.
The first idea, is simply to write it, very clearly, like this example:
function add(a, b) {
if (arguments.length < 1) {
return add;
} else if (arguments.length < 2) {
return function(c) { return a + c }
} else {
return a + b;
}
}
For the moment, lets ignore, that this is hideous, compared to ML, but lets just accept, that it does the same. The interface to the function has not changed, which is one of the benefits of currying.
Of course, you will need to understand the concept of closures, and how these work in JavaScript, before the example above makes much sense. Because JavaScript is weakly typed, we need to check on the number of arguments, and act accordingly.
arguments is the array, which internally in all functions,
represents an array of arguments passed to the function. The
length attribute gives the number. For more on
the arguments array, read on here.
if, we check to see if no arguments
were passed. If none were passed, we just return the function itself
back.c), and add that to the
a, that we got from the first function. The ability
of the returned function (which has no name if you look), to remember
the value of a is one of the principle ideas of closures,
and what makes all of this possible in JavaScript.a + b,
like we normally would.The curried adding function above, is fine you say, but isn't that a lot of code to change, just to get it do that? The function body, did grow from one line of code, into 6 lines (an explosion of 600%!) Yes, but there is also a way, of creating a generic solution. A solution which simply requires you paste a single line, into the top of any function you want curried.
I will now present a function, which you can use. I will first give it, and then present and example, and then go in depth in how it works.
function curry(func,args,space) {
var n = func.length - args.length; //arguments still to come
var sa = Array.prototype.slice.apply(args); // saved accumulator array
function accumulator(moreArgs,sa,n) {
var saPrev = sa.slice(0); // to reset
var nPrev = n; // to reset
for(var i=0;i<moreArgs.length;i++,n--) {
sa[sa.length] = moreArgs[i];
}
if ((n-moreArgs.length)<=0) {
var res = func.apply(space,sa);
// reset vars, so curried function can be applied to new params.
sa = saPrev;
n = nPrev;
return res;
} else {
return function (){
// arguments are params, so closure bussiness is avoided.
return accumulator(arguments,sa.slice(0),n);
}
}
}
return accumulator([],sa,n);
}
And here is now and example of how to use it. All it requires from you,
is a if clause in the top of the function, plus you need to edit in the
functions name. Of course, the function curry is a lot bigger,
then any code inside the first adding function I presented, but it's
totally generic, and be used every single time.
function add (a,b,c){
if (arguments.length < this.add.length) {
return curry(this.add,arguments,this);
}
return a+b+c;
}
alert(add()(1,2,4)); // 7
alert(add(1)(2)(5)); // 8
alert(add(1)()(2)()(6)); // 9
alert(add(1,2,7,8)); // 10
Let's first examine what happens, inside the actual function.
The if checks to see, if enough arguments where supplied.
And while the arguments array gives me the number
of arguments that were actually passed to the function,
<functionname>.length gives me the number of
arguments the function is defined with. That is, for the add
function above, add.length gives me three.
So, if not enough arguments where passed, it's time for the
curry function to come into action.
Inside the function curry is defined another function
accumulator, which does the very obvious thing
of accumulating the arguments.
The central thing, is the array sa, which contains the
arguments so far (saved arguments), and
then the function accumulator, which if called again, with
not enough arguments, will collect the new arguments into the array
sa, and then return, as the result, itself, so that
the next call, will also collect arguments. If enough arguments have
been collected, the function executes. Notice, that the apply
uses the closure space to execute in, this is very important,
as we shall see in a moment.
Also of importance, is how the arguments array is passed as an argument, to the new accumulator. Using closures, there is no real need to pass it, but using a closure, all curried functions, created like this, can only share the same arguments array! This is obviously not optimal, and there is no real solution I can see on this, which is why a copy of the array is passed instead of using closures.
In my old example, there was a bug in the code. After
enough arguments had been accumulated, the function was executed, just
as desired, but afterwards, the given arguments were not forgotten.
The new lines nPrev, and saPrev resets to the
originally captured values whenever the function has gotten enough
arguments. This returns the arguments to its pre-not-enough-arguments-yet,
each time it gets enough.
The function there, might look fine, but what if the function is really a method, and it depends on some property of it's host object? let's examine. First, we'll create a totally unlikely host object:
function container() {
var secret = 100; // lets see if this is caught
this.add = function (a,b,c){
if (arguments.length < this.add.length) {
return curry(this.add,arguments,this);
}
return a+b+c + secret;
}
this.adjustSecret = function (n) { secret = n; }
this.giveSecret = function() { return secret; }
}
The object container is perfectly normal object,
with a method add, and furthermore, it also has a property,
secret which is private to the object. I have give the object
some methods, to get and set this property, the methods
adjustSecret and giveSecret. Now, the goal is
to see, if we trick the method add into adding the wrong
secret to it's computation. This might seem easy, as the
curry function doesn't return the same function,
but actually a new function, and so forth.
con = new container();
alert("secret is : "+con.giveSecret()); // check that value is indeed 100
curriedthingy = con.add(1,2); // let's create a curried function
alert(curriedthingy(4)); // this alerts 107, as expected.
con.adjustSecret(1000); // now, in the original con object,
// we're adjusting the value to 1000,
// to check if it will be catched.
alert(curriedthingy(4)); // and presto, it does. alerts 1007.
This is of course, due to how when the curry function
is called, we also pass along the keyword this, which at all
times, represents the current object. Then, when we finally execute the
function, (using apply), we make sure to execute it as a
method of the closure passed along in this. This
ensures, that stuff like the above tricky is catched.
A little warning to the coder out there. You might have noticed, that I
use the slice method of the Array object, to
create a copy, and pass along to my new curry function. This isn't perfect,
as slice only creates a shallow copy. If a said entry in
an array contains an object reference, the newly created array will point
to the same object, as the original. This might lead to unintended side
effects. As I'm not aware of any way, to truly copy and object,
I don't know of any solution to this problem.
It's important to realize the limitations of the above posted generic solution. It doesn't do precompilation, which is one of the largest actual benefits of curried functions. All it does, is to provide syntactical sugar, and look fancy. So, what do to, if you want the function to do actual precompilation, which might be important in case of a large client side processing application?
I will give an example of a function, which often benefits from being curried. First I will present it in it's non-curried form, and I will then show how to easily transform it into a curried function, using nothing more then some if cases and nested functions.
The Horspool substring search algorithm is a simplification of the Boyer-Moore substring search algorithm. What it does, is that it searches for an occurrence of a pattern in a string, and then returns the indexes at which the pattern occurs (if it occurs at all).
While I won't go into depth about how the algorithm works (the linked page should do that fine), I'll just note, that the efficiency of the algorithm, comes from a table, that it builds up, before searching the string. The table indicate, how far ahead, the algorithm can skip, and still not miss an occurrence of the pattern. This table is entirely based on the pattern, and thus can be built, before the function is handed the string to search in.
The benefit, is that if you're going to look for a certain word, in several texts, this table doesn't have to be recalculated again and again, and you thus save processing time.
The functions String.toInt and
Array.compareTo are prototyped methods, and can
both be found here. toInt is to ease
the use of strings, as arrays of ints, while the compateTo
will actually compare to arrays, based on their contents.
([1,2]==[1,2] gives false in JavaScript normally
due to reasons too complex to cover here.)
function preBmBc(str,size) {
var bmBc = new Array(size);
var m = str.length;
for (var i = 0; i < bmBc.length; i++) { bmBc[i] = m; }
for (var i = 0; i < m-1; i++) {
bmBc[str[i]] = m - i - 1;
}
return bmBc;
}
function horspool(pat,str) {
var matches = new Array();
var m = pat.length;
var n = str.length;
var bmBc = preBmBc(pat,256);
var c, j = 0;
while (j <= n - m) {
c = str[j + m - 1];
if (pat[m - 1] == c) {
// first letter match. let's check the rest
if (pat.compareTo(str.slice(j,j + m))) {
matches.push(j);
}
}
j += bmBc[c];
}
return matches;
}
The function works something like this:
var text = "svend tofte is a user on the ars opentopic forums".toInt(); var pattern = "user".toInt(); var m = horspool(pattern,text); alert(m); // alerts 17
Of course, calling the horspool function like that,
doesn't save the table at all, and the processing time is essentially
wasted. I will now present a horspool function, which
is curried, and then talk about how it was done. The function
preBmBc is the same as above.
function horspool(pat,searchStr) {
if (arguments.length < 1) return horspool;
var bmBc = preBmBc(pat,256);
var m = pat.length;
function search(str) {
if (arguments.length < 1) return search;
var c, j = 0;
var n = str.length;
var matches = new Array();
while (j <= n - m) {
c = str[j + m - 1];
if (pat[m - 1] == c) {
// first letter match. let's check the rest
if (pat.compareTo(str.slice(j,j + m))) {
matches.push(j);
}
}
j += bmBc[c];
}
return matches;
}
if (arguments.length > 1) {
return search(searchStr);
} else {
return search;
}
}
The change, isn't unlike the first curried function I showed in JavaScript, in that it does verbose argument count checking, and acts on it.
If the function is called with no arguments, the very first
if catches it, and will return the function itself back.
Otherwise, we know that at least pat (pattern) was passed,
and we can build the table (using the function preBmBc).
We then define a function search, which does the actual pattern
matching. Note, that I made the function search have the
argument str, I had to rename the one in the function
horspool into searchStr, so as to avoid
these conflicting. Toward the end, we check, if searchStr
was also passed, if it was, we simply invoke search, and return
the array that it returns. If it wasn't passed, we simply return
search, knowing that it, due to JavaScript's closures, will
remember the table that was built for it (bmBc).
What's basically key here, is to wrap each nested call, in a function, and check on the number of arguments. This means, that if one has many arguments, the rewritten function will require just as many nested functions, to achieve true precompilation.
JavaScript being an interpreted language, just the advantage to doing it this way, would depend upon the actual implementation. It's a bit misleading to talk about precompilation, since that is a concept that doesn't really exist in JavaScript. We might want to call it preevaluation instead :)
Let's see an example of it's usage:
var haystack = "here is a needle in a haystack".toInt();
var anotherhaystack = "this is a totally different "+
"haystack with needle".toInt();
var needle = "needle".toInt();
var findNeedle = horspool(needle);
var m1 = findNeedle(haystack);
var m2 = findNeedle(anotherhaystack);
alert(m1); // shows 10
alert(m2); // shows 42
alert(horspool()(needle)()(haystack)); // shows 10
We've seen what curried functions truly are, a consequence of the Lambda calculus, and also how to go about writing these in JavaScript. I've presented a generic solution, which will give the syntactical advantages, and also presented an implementation of an algorithm, where the precompilation part will give actual CPU time benefits.