Currying and Partial Function Application

August 21, 2009

Two related but different concepts that you will run into when doing functional programming are currying and partial function application. People often don't understand the different between the two, I didn't myself until recently, but I think I've got a handle on in now. Currying and partial function application are two different things, but they go together like peanut butter and jelly.

First, let's start with currying. Currying is the process of transforming a function that takes n arguments into a function that takes n-1 arguments and returns a function. What the hell does that mean? Let's look at an example in everyone's favorite functional programming language, JavaScript.

Here's a simple function that returns true if the first argument is greater than the second argument:

function gt(x,y) {
  return x > y
}

Pretty basic. If we call gt(3,2), that will obviously return true. If we call gt(2) though, we get false, because it ends up evaluating the expression 2 > undefined, which is false. So our gt function is pretty useless unless you pass it two arguments.

Now what if we write it like this:

function gt(x,y) {
  if(arguments.length > 1) {
    return x > y
  } else {
    return function(z) {
      return z > x
    }
  }
}

Now there is a lot of crazy lambda calculus going on here. If you pass two arguments to gt, it works as before, returns true if x is greater than y. But if you pass just one argument, this function creates a function that takes one argument and returns true if the argument is greater than x.

This is an example of a closure. We say the function that is returned "closes over" x, which just means that the function remembers what the value of x was at the time it was created, so when you call it later, it still uses that value.

So if we call gt(2), the result we get back is a function that returns true if the argument to it is greater than 2. This is called partial function application.

In functional programming, the correct term is actually not "call a function", but "apply a function to a set arguments". That's why in JavaScript when you want call a function with arguments that you have in an array, you use the apply function, like this:

gt.apply(null,[3,2]))

The first argument to apply is the object that the reference this should point to during the function call, and in this case we just pass null because we don't care about the this reference. The next argument is the set of arguments, 3 and 2, which become the first and second arguments to the call to gt.

So now the term partial function application makes sense, because we are applying a partial list of arguments to the function. Now it should be clear why currying and partial function application go together hand-in-hand. When you partially apply a function that is curried, you get something useful back. Partially applying a function that is not curried isn't usually useful, as we saw in the first example, where calling gt(2) resulted in evaluating the expression 2 > undefined, which is just silly.

So in the case of our curried version of gt, is the result of partially applying actually useful? Sure it is, when we combined it with other functional concepts. All good functional programming language have some kind of filter function, and JavaScript (well, JavaScript 1.6. Better late than never) is no exception.

Filter is a higher-order function (whew, we are busting out all the fancy functional programming words today, aren't we!). It is a higher-order function because it takes another function as it's argument. What filter does is allow you to take an array of elements and produce another array with only the elements than match some condition. The function that defines what the condition is is typically a predicate function.

So let's filter an array of number an only get the ones greater than 2. First we'll do it with an anonymous function as the predicate function:

[0,1,2,3,4,5].filter(function(e){
  return e > 2
})

That will result in an array with 3, 4 and 5 in it. That's a little wordy though. Let's use our curried gt as the predicate instead:

[0,1,2,3,4,5].filter(gt(2))

Ah, there we go, that's nicer. That's gives us 3, 4 and 5 as well. Of course you can just change the value of the argument to gt to filter for values greater than that number.

Now I should point that technically, our gt function is not in fact partially applied when we pass in less than two arguments, it just makes a new function. If we define gt like this:

function gt(x) {
  return function(y) {
    return y > x
  }
}

This means that gt always takes two arguments and returns a function that takes one argument. This still works the same in our filter example, [0,1,2,3,4,5].filter(gt(2)) does the same thing. But when you want to just call gt directly with two arguments, that doesn't fly. gt(3,2) now just ignores the second argument and returns a function the same way gt(3) would. If we want to simulate our two argument call, we have to make two function calls, like gt(2)(3), which looks hideous. Not only do we have two sets of parentheses, it is also has to be backwards. To ask is 3 > 2, we has to pass in 2 first in order to the "greater than 2" function, and then pass 3 to that.

Haskell has built-in syntactic sugar to make this look not hideous. Haskell is a statically-typed functional programming language. Being statically-typed means that variables are of a specifc type. JavaScript is the opposite, dynamically-typed. In JavaScript, when you have a variable or a function argument that is named x, x can hold any type of Object, a String, Number, Function, etc. In Haskell, when you define a variable or function argument, that must always be the same type. Haskell is actually pretty clever about it though. If you just say x = 42, it knows, ok, x is an Int. In other, less sophisticated statically-typed languages, you would have to say something like int x = 42.

When you look at the type signature of a function in Haskell, at first, it looks odd. For example, the type signature for our gt function might look like:

gt :: Int -> Int -> Bool

At first you think, what's with the arrows? Wouldn't something like this make more sense:

gt :: (Int, Int) -> Bool

Yeah, that matches what we are thinking. gt is a function that takes two Int values and returns a Bool. Well, even though you might think of it that way, that's not what it does in Haskell. In Haskell, all functions are curried. So our gt function is actually much closer to our last definition of gt in JavaScript, which looks like this:

function gt(x) {
  return function(y) {
    return y > x
  }
}

If you look at that for a minute, you'll agree that a type signature like this makes sense.

gt :: Int -> Int -> Bool

gt takes one argument and returns a function that takes one argument that returns a Bool. Unlike JavaScript, Haskell's syntax makes calling curried functions clean. So again, in JavaScript, we would have to do this to call our function:

gt(2)(3)

Which is the same as 3 > 2, but in Haskell if we want that, we simply just say 3 > 2. In Haskell, infix operators are actually function calls. 3 > 2 is syntactic sugar for (>) 3 2. Also in Haskell, you don't have to wrap the function call in parentheses to call it. The parentheses in this snippet are just the way of getting a reference to the infix function without calling it. If you could name a function > in JavaScript, the Haskell snippet (>) 3 2, or even 3 > 2, would be the equivalent of >(3, 2) in JavaScript.

So when we want to partially apply this function to get a function that returns true if the value is greater than 2, we just write (> 2). Haskell knows how to "do the right thing" with infix functions like greater than, so we don't have to deal with the problem of the arguments being backwards. So here's how we do the filter, and we can do it by partially applying the built-in greater than function (this is the advantage of > being a function, not an operator) to get the "greater than 2 function" to pass to filter:

filter (> 2) [0..5]

This, of course, results in the list [3,4,5]. So that's a whirlwind tour of a lot of functional programming concepts, but we can sum it all up with this:

A curried function is a function that will return a new function when it is applied to less arguments than it expects and applying a function to less arguments than it expects is called partial function application. So, stated even more succinctly, a curried function is a function that will return a new function when it is partially applied.

Posted in Technology | Tags Javascript, Currying, PartialFunctionApplication, Closures, Haskell, FunctionalProgramming

Comments

1.

I had to over hover to see

less sophisticated statically-typed languages
. That was awesome.

I started reading on both Haskell and Clojure in the same week. Imagine that.

Keep up the good work.

# Posted By Neeraj on Friday, August 21 2009 at 8:58 PM

2.

Nice write-up. I've always been interested in functional programming, and things are finally coming together with Clojure and Haskell getting more attention.

Thank you for your interesting and informative blog.

# Posted By Frederic Daoud on Tuesday, August 25 2009 at 9:12 PM

Comments Disabled