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:
-
Fibonacci Numbers, Caching and Closures
- What's in
a Closure?
-
Using Automatic Memoization
- A Higher
Calling
- 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!