Oh! How I love that spicy Indian food!
Currying is a topic that I have wanted to cover in my C# 2.0 functional
programming series for quite awhile. In fact, it is one of the reasons I
decided to restrict this series to C# 2.0 in the first place. While curried
lambda expressions in C# 3.0 are extremely compact, they are difficult to
understand if you've never encountered them before. In contrast, C# 2.0's
verbosity actually helps to clarify the concept.
Since Visual Studio 2008 Beta 2 has been released and many people are
becoming more comfortable with it, you might see a little C# 3.0 slip in now and
then. However, this article will continue to use C# 2.0 as its main dialect.
Let's get started.
What, Exactly, Is This "Currying" Thing?
First of all, currying has nothing to do with Indian or Thai food. It is
named after the logician
Haskell Curry (for whom the fabulous functional programming language,
Haskell, also is named). The term refers to a special technique found in both
mathematical logic and computer science.
The HaskellWiki
defines currying as "the process of transforming a function that takes multiple
arguments into a function that takes just a single argument and returns another
function if any arguments are still needed." Errr... come again?
OK. Suppose that we have a simple function that takes two arguments and
returns a value.
class Program
{
delegate int Operation(int x, int
y);
static void Main()
{
Operation add = delegate(int x, int y)
{
return x + y;
};
Console.WriteLine(add(13, 29));
}
}
Here we use an anonymous delegate to create a function that performs simple
addition. This function takes two arguments, x and y, and returns a value, their
sum.
To curry, we will transform our two-argument function into a single-argument
function using a pair of anonymous delegates. The first delegate takes x and
returns a second delegate which takes y. The second delegate actually contains
the meat of the function and performs the addition of x and y.
class Program
{
delegate CurriedOperation2 CurriedOperation(int x);
delegate int CurriedOperation2(int
y);
static void Main()
{
CurriedOperation add = delegate(int x)
{
return delegate(int y)
{
return x + y;
};
};
Console.WriteLine(add(13)(29));
}
}
Notice that the inner delegate can reference the argument x from the outer
delegate through the principle of
closure. This
point will become very important a bit later. In addition, we have to change the way
in which we call the add function. Extra parentheses must be used because we are
now calling two functions instead of one.
The process of currying a function is not particularly difficult, but it
requires a bit of thought. It would be useful to create some sort of
general-purpose "Curry" function. This would be a
higher-order
function that takes an Operation delegate and returns a CurriedOperation
delegate, performing the curry process for us.
class Program
{
delegate int Operation(int x, int y);
delegate CurriedOperation2 CurriedOperation(int x);
delegate int CurriedOperation2(int
y);
static CurriedOperation Curry(Operation op)
{
return delegate(int x)
{
return delegate(int y)
{
return op(x, y);
};
};
}
static void Main()
{
Operation add = delegate(int x, int y)
{
return x + y;
};
CurriedOperation curriedAdd
= Curry(add);
Console.WriteLine(curriedAdd(13)(29));
}
}
This successfully makes the currying process more general purpose, but it is
still tightly coupled to the types on which the delegates operate. To correct
this, we should use C# 2.0 generics to parameterize by type. Introducing
generics can be complicated, so let's start with our first example of the
currying process.
class Program
{
delegate TResult Func<TArg, TResult>(TArg
a);
static void Main()
{
Func<int, Func<int, int>> add = delegate(int x)
{
return delegate(int y)
{
return x + y;
};
};
Console.WriteLine(add(13)(29));
}
}
The Func<int, Func<int, int>> syntax might look a little daunting at first,
but using generics recursively only requires one delegate type instead of two.
Essentially, we're defining a delegate that takes an int and returns a delegate
that takes an int and returns an int. Got it? Other than that, the code is
essentially the same.
Moving on to the more general-purpose solution...
class Program
{
delegate TResult Func<TArg1, TArg2, TResult>(TArg1 a1, TArg2 a2);
delegate TResult Func<TArg, TResult>(TArg
a);
static Func<TArg1, Func<TArg2, TResult>> Curry<TArg1, TArg2, TResult>(Func<TArg1, TArg2, TResult> f)
{
return delegate(TArg1 a1)
{
return delegate(TArg2 a2)
{
return f(a1, a2);
};
};
}
static void Main()
{
Func<int, int, int> add = delegate(int x, int y)
{
return x + y;
};
Func<int, Func<int, int>> curriedAdd
= Curry(add);
Console.WriteLine(curriedAdd(13)(29));
}
}
Look carefully at this code. Sometimes it can be challenging to see the
"forest for the angle brackets." However, the introduction of generics provides
us with a function that can be used to curry two-argument functions of any
type. Besides, most of the generic code can be shuffled off to a library,
leaving the client code relatively simple.
Earlier, I mentioned that currying is much more concise in C# 3.0. Here's a
translation of the last code sample to prove my claim.
static class Program
{
static Func<TArg1, Func<TArg2, TResult>> Curry<TArg1, TArg2, TResult>(this Func<TArg1, TArg2, TResult> f)
{
return a1 => a2 => f(a1, a2);
}
static void Main()
{
Func<int, int, int>
add = (x, y) => x + y;
var curriedAdd = add.Curry();
Console.WriteLine(curriedAdd(13)(29));
}
}
First of all, we can remove the declarations of the Func<...> delegate types
because they already exist in the C# 3.0 libraries. In addition, the conciseness
of lambda expressions makes our anonymous delegates look like big, ugly brutes
by comparison. Finally, C# 3.0 type inference takes care of the hideous Func<int,
Func<int, int>> type through use of the "var" keyword. As icing on the cake, the
Curry function can be turned into an extension method and called as if it were a
member of "add."
The double-arrow-lambda-expression-thingy might look foreign until you
realize that it actually represents two functions. So, the conciseness
of C# 3.0 comes at the small price of a little familiarity.
What's the Point of All This?
The value of currying a function lies in what you intend to do with
it afterward. Used wisely, curried functions can be building blocks in the creation
of other functions. Consider the following code:
static void Main()
{
Func<int, int, int> add = delegate(int x, int y)
{
return x + y;
};
Func<int, Func<int, int>> curriedAdd
= Curry(add);
Func<int, int> increment = curriedAdd(1);
Console.WriteLine(increment(41));
}
Here, we pass 1 to our curried "add" function and create a new function,
"increment." The "increment" function is really just a reference to the inner
delegate of the curried "add" function with x bound to the value of 1 through
closure. This
technique is known as partial application and is extremely powerful. (At the time of this writing, the
Wikipedia article on
currying doesn't distinguish between currying and partial application, but they
are clearly different
activities.)
Next time, we'll look deeper into partial application. The example in this
article is simple but contrived, and it doesn't delve deeply enough into the
possibilities. In the next article, we'll look at some truly useful examples of
currying combined with partial application.