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.

Currying, what?

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.

A crash course in ML

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.

Variables in ML

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.

Functions in ML

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

Anonymous functions in ML

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

The truth about anonymous functions

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.

How to write curried 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.

  1. In the first if, we check to see if no arguments were passed. If none were passed, we just return the function itself back.
  2. If one argument was passed, we return a new function, which in turn will expect one new argument (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.
  3. If both arguments are passed at once, we just return a + b, like we normally would.

Now that wasn't very generic now was it?

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.

How this works in a closure

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

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.

Precompilation and an example

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

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.

Horspool in JavaScript

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

Conclusions

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.