I have moved my active blog over to tumblr. I've maintained this blog for reference but will be posting to http://www.robustsoftware.co.uk instead. I've pointed my Feedburner feed to tumblr so if you're subscribed already you should already have switched with me.

Currying with C#

At the Brighton altnetbeers on Tuesday night we ended up talking quite a bit about functional languages. One of the concepts I often forget the meaning of is currying. Mike Hadlow was kind enough to remind me of what it was and I thought I’d write a blog post explaining what it was in terms of C# to help me remember in the future.

Currying is what happens when you call a function without providing all the required parameters. Instead of failing to compile functional languages such as F# will instead return a function that takes the unspecified arguments as parameters.

Now that probably makes bugger all sense without knowing what currying is in the first place. As this is meant to be an explanation I’ll show you an example of how we can emulate currying in C#. This is almost better than showing you it in a functional language as it will show the nuts and bolts of what functional languages do for you.

I’ll be dropping my usual use of var as specifying the types should make it easier to follow what’s going on.

We’ll start with a simple method to add two numbers together:

int Sum(int x, int y)
{
return x + y;
}

At the moment we can only call our method by providing both arguments:

int sum = Sum(2, 3);

What currying does is create an overload that lets you call the method with one argument. But rather than pass a default value for the second argument and call the original function, it instead returns a function that will provide the second argument.

Wow, this is hard to explain in words. Maybe some code will make it clearer:

Func<int, int> Sum(int x)
{
return y => Sum(x, y);
}

This lets you store an instance of a function that performs a certain manipulation like this:

Func<int, int> addTwo = Sum(2);

int three = addTwo(1);
int five = addTwo(3);

With a single function this is a novelty. The power comes when you can curry functions together. To demonstrate this we'll need to add a multiply method:

int Multiply(int x, int y)
{
return x * y;
}

Func<int, int> Multiply(int x)
{
return y => Multiply(x, y);
}

Functional languages also let you specify functions as arguments in place of specific values. That starts getting a little trickier to emulate in C#:

An hour or two passes whilst I work out how to do this!

It took me a while to work it out but you need to get a whole lot more functional to do this bit. That means all our methods have to start using Func<int> instead of plain int. In hindsight this was obvious because in functional languages everything is a function, hence the name. Even numbers are represented by functions that return the number in question rather than the number itself, referred to as literals.

This is what this actually looks like:

Func<int> Sum(Func<int> x, Func<int> y)
{
return Literal(x() + y());
}

Func<Func<int>, Func<int>> Sum(Func<int> x)
{
return y => Sum(x, y);
}

Func<int> Multiply(Func<int> x, Func<int> y)
{
return Literal(x() * y());
}

Func<Func<int>, Func<int>> Multiply(Func<int> x)
{
return y => Multiply(x, y);
}

Func<int> Literal(int x)
{
return () => x;
}

The literal method isn’t really required but makes the code a lot clearer rather than having empty lambdas dotted about the place.

To take a step back for a second our original sums:

Func<int, int> addTwo = Sum(2);

int three = addTwo(1);
int five = addTwo(3);

Will now look like this:

Func<Func<int>, Func<int>> addTwo = Sum(Literal(2));

Func<int> three = addTwo(Literal(1));
Func<int> five = addTwo(Literal(3));

It's more verbose but it lets us curry functions together which was our original aim.

On to the currying function itself. Now if you're allergic to angled brackets and lambdas you are going to want to skip this chunk of code. It's pretty awesome horrendous.

Func<Func<int>, Func<int>> Curry(Func<Func<int>, Func<int>> x, Func<Func<int>, Func<int>> y)
{
return a => y(x(a));
}

What this is doing is creating a new function which when it gets passed a literal it determines the result of invoking the x function and returns the result of passing that on to the y function. Again, an example will probably help demonstrate what's going on.

Func<Func<int>, Func<int>> addTwo = Sum(Literal(2));
Func<Func<int>, Func<int>> timesThree = Multiply(Literal(3));
Func<Func<int>, Func<int>> addTwoTimesThree = Curry(addTwo, timesThree);

Func<int> twentyOne = addTwoTimesThree(Literal(5));

Now because of how the code is now structured we could keep nesting these simple functions together to create much more complex functions. This is the root of the power of functional languages.

Well that was interesting. I definitely understand currying and functional languages a bit better now and I hope someone else has learnt something in the process.

I’ve put a full code listing up on gist in case anyone wants to grab it and play about with it.