Functional JavaScript – Currying

Introduction

Simply put, currying is the means for reducing the arity of a function. That’s it. If prior to currying a function accepted n parameters then after currying a new function will have been created accepting fewer than n parameters. Usually the goal is to reduce the function to a monadic form, i.e. having an arity of 1.

Why would anyone want to do this? The reason usually provided is some languages such as lambda calculus, Haskell, and ML only allow you to define functions accepting one parameter. What if you need a function accepting more than one parameter? Then you’re out of luck—unless you use currying.

Falling Factorial

Consider this implementation of the falling factorial function which is used to efficiently calculate binomial coefficients:

function FallingFactorial(x, n) {
  if (n == 0) return 1;
  return (x - (n - 1)) * FallingFactorial(x, n-1);
}

Observe this implementation has an arity of 2 and is recursively defined. As an aside you might also observe that FallingFactorial(n, n) == n!.

Currying

The process of currying is straightforward. To create a monadic implementation of falling factorial we need to create a function accepting x as a parameter which returns a new function closed over x and accepting n as a parameter which computes and returns the result. Look at this example:

function CurriedFallingFactorial(x) {
  return function(n) {
    if (n == 0) return 1;
    return (x - (n - 1)) * CurriedFallingFactorial(x)(n-1);
  }
}

The function CurriedFallingFactorial accepts one parameter, x, and returns a function accepting one parameter, n. Since the returned function refers to x in its implementation it’s said to be closed over x and as such this kind of function is referred to as a closure. The returned function has access to both x and n and so can complete the implementation and return the desired result so that

FallingFactorial(x, n) == CurriedFallingFactorial(x)(n)

The astute JavaScript developer will recognize the recursive invocation of CurriedFallingFactorial will generate a lot of anonymous functions (on the heap, no less!), all closed over the same value of x, i.e. all having the exact same implementation. Once you’ve obtained an instance of the returned function closed over x you can recursively invoke it rather than continuing to recreate it and invoke it as the following implementation illustrates:

function CurriedFallingFactorial(x) {
  return function(n) {
    if (n == 0) return 1;
    return (x - (n - 1)) * arguments.callee(n-1);
  }
}

arguments.callee is the means for obtaining a reference to the currently executing function, which in this case is already closed over x.

Motivation

Why would you ever curry a JavaScript function since it may accept however many parameters as needed? Function adaptation. Functional JavaScript—Memoization, Part I presents a memoization implementation that only works on unary or monadic functions. In that post I said “There’s an elegant solution for memoizing functions of higher arity that I’ll be demonstrating in a future post.” This is that post, and currying is the elegant solution.

So how do we begin to go about memoizing CurriedFallingFactorial? We first note a rather peculiar property of CurriedFallingFactorial as it’s currently implemented:

CurriedFallingFactorial(x) != CurriedFallingFactorial(x)

This is not to be confused with the following expression which is true:

CurriedFallingFactorial(x)(n) == CurriedFallingFactorial(x)(n)

The reason for this anomaly is what prompted us to implement the CurriedFallingFactorial more efficiently—every time you call CurriedFallingFactorial a newly-created anonymous function closed over x is returned, even when provided the same values for x. That is why CurriedFallingFactorial(x) != CurriedFallingFactorial(x). We’ll begin our memoization implementation by addressing this anomaly.

function MemoizedCurriedFallingFactorial(x) {

  if (MemoizedCurriedFallingFactorial.memoizer == null) {
    MemoizedCurriedFallingFactorial.memoizer = function(x) {
      return function(n) {
        if (n == 0) return 1;
          return (x - (n - 1)) * arguments.callee(n-1);
        }
    }.memoize().memoizer;  // function(x) memoizer
  }

  // delegate to memoized implementation of function(x)
  return MemoizedCurriedFallingFactorial.memoizer.fn(x);
}

I’ve highlighted the heart of the implementation. I’ve created a new anonymous function accepting x and then memoize that implementation which I in turn assign to the memoizer property of the MemoizedCurriedFallingFactorial function. The implementation of MemoizedCurriedFallingFactorial delegates to the memoized implementation of this anonymous function accepting x.

As in the previous implementation the anonymous function accepting n is closed over x and so we can optimize its recursive invocation by using arguments.callee to refer to itself rather than re-invoking MemoizedCurriedFallingFactorial(x) to obtain a (memoized) reference to itself.

The upshot of this change is that MemoizedCurriedFallingFactorial(x) == MemoizedCurriedFallingFactorial(x).

We’re not finished though. We need to address the anonymous function accepting n that is closed over x, we must memoize this implementation as well.

function MemoizedCurriedFallingFactorial(x) {

  if (MemoizedCurriedFallingFactorial.memoizer == null) {
    MemoizedCurriedFallingFactorial.memoizer = function(x) {
      var anon = function(n) {
        if (n == 0) return 1;
          return (x - (n - 1)) * anon(n-1);
        }.memoize();  // memoize function(n)
        return anon;  // return memoized function(n)
    }.memoize().memoizer; // function(x) memoizer
  }

  // delegate to memoized implementation of function(x)
  return MemoizedCurriedFallingFactorial.memoizer.fn(x);
}

Once again the interesting code is highlighted. This implementation additionally memoizes the anonymous function accepting n. Notice we’ve assigned this anonymous function to the variable anon so that we may recursively reference our memoized form in line 7. The anonymous function is closed over both x and anon.

Conclusion

If you need to memoize a function accepting more than one parameter then consider currying as a function adapter as a means for doing so. Such function adaptation is the primary motivator for currying in JavaScript.

More to Explore

Functional JavaScript — Memoization, Part I
Functional JavaScript — Memoization, Part II
Functional JavaScript — Tail Call Optimization and Trampolines
Functional JavaScript — Tail Call Optimization and Babel