Thursday, September 20, 2007
If you've been keeping count, this is the sixth article in my series on functional programming ideas using C# 2.0. If this series is new to you, here are links to the previous articles (in order) to help you get started:
  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.

static void Main()
{
  Func<int, Func<int, int>> add = delegate(int x)
  {
    return delegate(int y)
    {
      return x + y;
    };
  };
 
  int value = add(1)(41);
 
  Console.WriteLine(value);
}

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:

static void Main()
{
  Func<int, Func<int, int>> add = delegate(int x)
  {
    return delegate(int y)
    {
      return x + y;
    };
  };
 
  Func<int, int> increment = add(1);
 
  int value = increment(41);
 
  Console.WriteLine(value);
}

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.

NeRd Note
Curious about how that code would look in a functional programming language where currying is implicit? Here it is in F#:
let add x y = x + y
let increment = add 1
let value  = increment 41
 
printfn "%i" value
OK. Moving on...

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:

static bool IsPrime(int value)
{
  int max = (value / 2) + 1;
  for (int i = 2; i < max; i++)
    if ((value % i) == 0)
      return false;
 
  return true;
}
 
static void Main()
{
  int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
 
  Console.Write("Primes:");
  foreach (int n in HigherOrder.Filter(IsPrime, numbers))
    Console.Write(" {0}", n);
  Console.WriteLine();
}

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!

static void Main()
{
  Func<Func<int, bool>, IEnumerable<int>, IEnumerable<int>> filter = HigherOrder.Filter<int>;
  Func<Func<int, bool>, Func<IEnumerable<int>, IEnumerable<int>>> curriedFilter = HigherOrder.Curry(filter);
  Func<IEnumerable<int>, IEnumerable<int>> getPrimes = curriedFilter(IsPrime);
 
  int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
 
  Console.Write("Primes:");
  foreach (int n in getPrimes(numbers))
    Console.Write(" {0}", n);
  Console.WriteLine();
}

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:

static void Main()
{
  var filter = HigherOrder.GetFilter<int>().Curry();
  var getPrimes = filter(IsPrime);
 
  int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
 
  Console.Write("Primes:");
  foreach (int n in getPrimes(numbers))
    Console.Write(" {0}", n);
  Console.WriteLine();
}

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:

static readonly Func<IEnumerable<int>, IEnumerable<int>> GetPrimes =
  HigherOrder.GetFilter<int>().Curry()(IsPrime);
 
static void Main()
{
  int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
 
  Console.Write("Primes:");
  foreach (int n in GetPrimes(numbers))
    Console.Write(" {0}", n);
  Console.WriteLine();
}

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.

var reduce = HigherOrder.GetReduce<long>().Curry();
var getProduct = reduce((x, y) => x * y)(1);

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.

static void Main()
{
  var reduce = HigherOrder.GetReduce<long>().Curry();
  var getProduct = reduce((x, y) => x * y)(1);
 
  var factorialOf10 = getProduct(new long[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
 
  Console.WriteLine("Factorial of 10 is {0:#,#}", factorialOf10);
}

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:

public static IEnumerable<TSource> Sequence<TSource>(Func<TSource, TSource> getNext,
  TSource startValue, Func<TSource, bool> shouldStop)
{
  if (getNext == null)
    yield break;
 
  TSource result = startValue;
  yield return result;
 
  while (true)
  {
    if (shouldStop != null && !shouldStop(result))
      break;

    result = getNext(result);
    yield return result;
  }
}

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.

var sequence = HigherOrder.GetSequence<long>().Curry();
var numbersFromOneToX = sequence(x => ++x)(1);

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

static void Main()
{
  var reduce = HigherOrder.GetReduce<long>().Curry();
  var getProduct = reduce((x, y) => x * y)(1);
 
  var sequence = HigherOrder.GetSequence<long>().Curry();
  var numbersFromOneToX = sequence(x => ++x)(1);
 
  var factorialOf10 = getProduct(numbersFromOneToX(x => x == 10));
 
  Console.WriteLine("Factorial of 10 is {0:#,#}", factorialOf10);
}

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

static void Main()
{
  var reduce = HigherOrder.GetReduce<long>().Curry();
  var getProduct = reduce((x, y) => x * y)(1);
 
  var sequence = HigherOrder.GetSequence<long>().Curry();
  var numbersFromOneToX = sequence(x => ++x)(1);
 
  var factorial = /* Something really, really, really cool must go here. */;
 
  var factorialOf10 = factorial(10);
 
  Console.WriteLine("Factorial of 10 is {0:#,#}", factorialOf10);
}

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!

posted on Thursday, September 20, 2007 7:43:07 AM (Pacific Standard Time, UTC-08:00)  #    Comments [0]

kick it on DotNetKicks.com