1. Fibonacci Numbers, Caching and Closures
2. What's in a Closure?
3. Using Automatic Memoization
4. A Higher Calling
5. The Art of Currying

I've decided that it's time for an upgrade. While the ideas in this article can be compiled successfully in C# 2.0, they don't always look pretty. In fact, they often have deeply-nested, over-complicated generic delegate types (e.g. Func<Func<int, int, int>, Func<int, Func<IEnumerable<int>, int>>>). These have the effect of severely decreasing the readability of the code and obfuscating the ideas that I'm trying to present. Because of this, I'll shift to C# 3.0 about halfway through. If you happen to be one who breaks out in cold sweats at the mention of the word "lambda," feel free to take a look at my coverage of lambda expressions.

A Brief Recap

Last time, I may have left some of you wanting more. Actually, I hope that I left you wanting more. Currying may be an interesting concept (and is absolutely essential in the Lambda Calculus), but it doesn't really justify itself as a useful programming technique. In reality, it is a stepping stone towards more practical techniques.

Simply put, currying is the process of converting a function of two or more arguments into a function of just one argument. Here's how we might define and use a curried function that adds two integers.

Near the very end of the previous article, I hinted at one good reason for currying a function: partial application. The idea is to pass only some of the arguments to a function. When a function is curried, it returns another function whose signature contains the remaining arguments. The arguments that have already been passed are fixed through a lexical closure. Confused? Consider this minor modification to the previous example:

Instead of calling "add" with both arguments, we partially apply the first argument and store the function that it returns in a variable called "increment." This new "increment" variable is actually a brand new function built from the curried "add" function!

What? That doesn't excite you? Well, I suppose the example is wildly contrived... I mean, who would ever write that? The problem is that this is really a text book example, and it doesn't convey the true power of currying combined with partial application. What is needed are some truly useful examples. Otherwise, this is all just a computer-science parlor trick.

Partially Applying Curried Higher-Order Functions (whew!)

Currying + Partial Application becomes extraordinarily powerful when used with Higher-Order Functions. Consider this sample, which outputs the prime numbers from an array of integers:

Here we call the higher-order Filter function with a predicate that checks to see if a particular number is prime. If Filter were curried, we could partially apply the predicate and create a brand new function that filters out prime numbers. Here's how we might do this:

Warning! Complex generics ahead! Do not adjust your screen!

That actually makes my head hurt a bit. It isn't too hard to look at now, but it was terribly painful to write. Fortunately, this is the sort of thing that C# 3.0 can make beautiful. After creating a helper function that produces a delegate for Filter and making Curry an extension method, we can write this:

Now we're cookin' with gas! If we need the "getPrimes" function to be scoped at the class level, we can use a static, readonly field (or even a property) like this:

Regardless of the syntax chosen, we shouldn't lose sight of what's really happening here: we're building functions from other functions. This is really the meat-and-potatoes of functional programming, and I want to make sure it isn't lost in the technical details.

A More Complicated Example

To ensure that we all understand the concept, let's take a look at one more example. Using what we've learned so far, how might we build the factorial function?

At the heart of the algorithm, factorial is just the reduction of a sequence using multiplication. With that in mind, we should be able to curry and partially apply our Reduce higher-order function to create a new function that calculates the product of a sequence of numbers.

This gets us pretty close. We now have a "getProduct" function that takes an IEnumerable<long> and returns the product of its elements. At this point, we could calculate factorial simply by passing an array of integer values into the function, assuming the integers were sequential and started from 1.

However, that really isn't the factorial function. We need some way to ensure that the sequence passed to "getProduct" is truly sequential and starts from one. To do this, we'll use another higher-order function, Sequence:

Sequence is really just an abstraction of a loop. It takes a starting value, a function that retrieves subsequent values and a function that determines when the sequence should end. In addition, because Sequence is implemented with a C# iterator, it is truly lazy and could, technically, run forever. So, it should be used with care!

A quick curry and partial application of Sequence builds us a new function that produces a sequence of integers starting from one.

We can use this new "numbersFromOneToX" function with our "getProduct" function to calculate factorial.

This is a bit closer, but it still isn't a factorial function. What we'd really like is to get something like this:

I know that you're all clamoring for me to fill in the missing piece, but that will have to wait until next time. It's true that factorial really can be built from this, but it will require yet another concept: function composition.

If you would like to play with the code presented in this article, you can download my HigherOrder class here. There are two versions included: one for C# 2.0 and one for C# 3.0. Have fun!