The Many Flavors of Curry

August 31st, 2009

3

Many functional languages have this nifty feature called ‘currying’ or ‘curried functions’. The name comes from the logician Haskell Curry (son of Samuel Silas Curry — someone please hook me up with wherever they are getting these names!), for whom the Haskell programming language is also named.

Currying is a technique for making partial applications of functions first class objects in an intuitive way. To demonstrate, suppose that you had a function of three numbers, f(x, y, z) = x * y + z. Written like this, you need all the variables x, y, and z to apply the function and get the answer. But suppose you just know that x = 5. Well, you could rewrite f(x, y, z) as f-with-x-equal-5(y, z) = 5 * y + z. That way, if your friend Alice knows y and z and wants to compute the value of f(x, y, z), you can give Alice f-with x-equal-5(y, z), and she can do the rest. You don’t need to give her the values of f(x, y, z) and x, which, in some bizarre universe (such as the Haskell programming language), could save some book-keeping. We call f-with-x-equal-5(y, z) a “partially-applied” version of f(x, y, z).

To take this idea a step further, we could bake this concept right into the definition of f(x, y, z), by making f-x-y-z(x) be a function that returned f-with-x-equal-something-y-z(y), which in turn would be a function that returned f-with-x-equal something-and-y-equal-something-else-z(z). In the notation of the lambda calculus, it might look something like this:

This would be a strange thing to do in Perl or python, but in Haskell, most functions are like this in the wild. The style of currying used in Haskell is also found in OCaml and other ml-derived languages. It is the most vanilla curry. In Haskell, it’s actually easier to define f-x-y-z, the curried version of f, than it is to define f. For brevity, I’ll start calling f-x-y-z fc. The definitions of f and fc looks something like this in Haskell:

You would then call fc any of the following ways to get something useful:

Currying helps avoid unnecessary re-definition of common functions when you’re mapping or filtering over lists in simple ways. For example, suppose you want to remove the zeros from a list of numbers. In Perl, you would do this:

Or this in Ruby:

This would be the equivalent of this in Haskell:

But in Haskell, (\x -> 0 /= x) is redundant because the operator (/=) is a curried function! So you can just write:

If you had a list of z values for the fc function, you could compute fc 5 4 z for each of them with just:

There’s no need to specify an explicit lambda expression (called a block in Perl and Ruby, or anonymous function in javascript) here, because fc 5 4 is a function already.

Cut

Currying in Haskell and OCaml is great, because these languages provide a compact syntax for function application that is conducive to curryied functions (a b is a applied to b, a b c is a applied to b applied to c, et c), but for languages with a lisp-like syntax, currying is visually obnoxious. If we take the curried fc above and write it in Scheme, it would look like:

And then to apply fc:

as compared with applying and defining f uncurried:

The curried version still looks cleaner in in the map that we did earlier in Haskell:

The definition and application of curried functions still requires a lot of syntax overhead, even for Scheme (zing!).

Enter cut. (This last sentence should hopefully confuse the Hollywood movie business folks.) The need for curry-like behavior in Scheme has been recognized, and the result is the function called cut, defined in SRFI-26 (A SRFI is a Scheme Request For Implementation — something like a ratified mini-standard for Scheme). According to the SRFI (srfi.schemers.org/srfi-26/srfi-26.html), you can think of cut as “Curry Upon This,” which betrays that currying was a significant inspiration for this Scheme feature.

Cut allows you to take a function and partially apply any arguments, without any requirements that the function be written in a curried style. For example, using our old uncurried f, we can map over our list like this:

The <> is cut’s syntax to indicate an argument that is yet to be bound. Thus (cut f <> <> <>) is just f, and (cut f <> 4 <>) is a version of f that expects the arguments x and z in that order. Cut does not provide a syntax for re-ordering arguments, because at that point it would be re-implementing Scheme’s lambda expression syntax, and the point is to get away from having to use lambda!

So, cut is the perfect compromise in Scheme between the overhead of defining curried functions explicitly, and the facility of easy access to partially-applied functions. cut is also more general than curring in a certain way, because you do not need to partially apply the function arguments in a particular order, thus, we could just as easily write

If we had a list of x’s instead of a list of z’s. We could do the same thing in Haskell with the ‘flip’ function that swaps the first two arguments to a curried function, but it can get confusing when curried functions take more than two arguments. To do the same thing as above, we would have to say:

Yikes! At that point, (\x > f x 4 3) is shorter and cleaner.

Cut in JavaScript

In summary, some facility for having partially applied functions is a great feature for any language that has first-class functions at all. Currying works great for Haskell, and cut works well for Scheme. As far as I’m aware, Perl lacks a convenient syntax for partially applying subroutines - at least, no syntax has ever persuaded me to start using it in my Perl code despite using higher-order functions frequently.

JavaScript is certainly without any facility for partially applying functions. Furthermore, Javascript’s lambda (anonynous function) syntax is absolutely ghastly. Lets see just how badly javascript loses at code golf in our now-familiar map example:

Believe me, this javascript syntax gets old when you do it five times per day. I mean really, more syntax overhead than Scheme! (zing 2!) Luckily, we can write our own cut function in JavaScript to sometimes save ourselves from using the awful ‘function’ syntax:

So if we write the uncurried f in javascript, as in Scheme:

(as javascript again fails to win any prizes for terseness), then we can condense our map code in javascript back to the order of magnitude of length in the other languages:

turns into:

In case you’re keeping the score on the code golf, note that our cut syntax allows javascript to tie Scheme for last place! This is one of the many things we do to use functional idioms to make javascript development tolerable, or even if I dare say, fun and interesting, here at Border Stylo. I challenge you to implement some neat partial function application framework in your language of choice (python!) and send me the results!

Tagged with: Haskell, Scheme, javascript, lambda, syntax

Related Posts

• Browser Wars 2.0 - the Plug-in
• Poor Man's Webspider
• Stateless Tests in a Stateful Protocol
• YAJ: Yet Another Javascript?
• Javascript dependency management made easy like Sunday morning
• Types and Type Theory (part 2)
• Gems in Scheme

Author