Thursday, March 13, 2008

Currying in C# with Oliver Sturm

I really enjoyed last night's talk at the London DNUG by Oliver Sturm titled 'Functional programming with C#'. I had a genuine 'I did not know you could do that' moment when he showed us how to do Currying in C#. Of course there was much more to the talk than that, including lambda expressions, closures and map-filter-reduce, but they were less of a surprise. Still an excellent explanation of all things functional.

So, what's currying? Well it's got nothing to do with vindaloo, it's a really simple idea which basically says that if you give a function less arguments than it expects you get back another function that only expects the missing arguments. Now, of course if you give a function in C# less arguments than it expects you get a compilation error. What Oliver showed us was that its trivially easy to write a 'Curry' function that will return any function you give it in a curried version. You can curry to your hearts content.

OK, so lambda expressions give us this great syntax for creating anonymous delegates, or little functions you can assign to a variable. Here's a trivial example; add:

Func<int, int, int> add = (x, y) => x + y;
int a = add(2, 3);  // a = 5

You use the add function like any other. Here we're adding 2 and 3 and returning 5. Now we can also use the lambda syntax to build an add function that within it returns a function that's just waiting for the other side of the add expression. OK, that's gobbledygook, it's easier to show than explain:

Func<int, Func<int, int>> curriedAdd = x => y => x + y;
int b = curriedAdd(2)(3); // b = 5

The result is the same, it's just that the syntax looks unfamiliar. Now we can curry our curriedAdd by just supplying one argument and then use our new add5 function as many times as we want:

var add5 = curriedAdd(5);

int c = add5(3); // c = 8
int d = add5(5); // d = 10

But you don't have to explicitly define your curried function when you've got a 'Curry' function that will create it for you. Here's another stupidly trivial example: We've got a function called addFourThings, we pass it into our Curry function and out pops curriedAddFourThings. We can use that to simply add four numbers, or we can progressively assign the arguments one at a time.

Func<int, int, int, int, int> addFourThings = (a, b, c, d) => a + b + c + d;

var curriedAddFourThings = Curry(addFourThings);

int result = curriedAddFourThings(1)(2)(3)(4);  // result = 10

var addOne = curriedAddFourThings(1);
var addOneAndTwo = addOne(2);
var addOneAndTwoAndThree = addOneAndTwo(3);

int result2 = addOneAndTwoAndThree(4); // result2 = 10

Here is Oliver's set of Curry function overloads.

public Func<T1, Func<T2, T3>> Curry<T1, T2, T3>(Func<T1, T2, T3> function)
{
    return a => b => function(a, b);
}

public Func<T1, Func<T2, Func<T3, T4>>> Curry<T1, T2, T3, T4>(Func<T1, T2, T3, T4> function)
{
    return a => b => c => function(a, b, c);
}

public Func<T1, Func<T2, Func<T3, Func<T4, T5>>>> Curry<T1, T2, T3, T4, T5>(Func<T1, T2, T3, T4, T5> function)
{
    return a => b => c => d => function(a, b, c, d);
}

Pretty simple eh. This is all very neat, and I can imagine how it could be very useful in factoring algorithms. Oliver showed us an example in his talk. But I think I'm going to need to see a few more cases of it being used in real world situations and maybe try it out a few times before it becomes a natural part of my programming toolkit.

8 comments:

Anonymous said...

ouch. I don't understand.

Anonymous said...

Re-implementing something that has been around for decades is hardly interesting. It's just syntactic sugar. I know that some people are eager to put this on their CV so they will probably re-write their entire codebase, using this and other such C# 3.0/4.0 constructs, which is sad really. Using currying for anything other than the simplest examples is wrong, as we have things called methods which are much cleaner, clearer and understandable:
int Add(int x, int y)
{
return x+y;
}

see?

Mike Hadlow said...

Anonymous,

I liked your comment so much that I've devoted an entire post to it:

http://mikehadlow.blogspot.com/2010/03/why-i-write-this-stuff.html

James Curran said...

Anonymous:
var searchKey = 'James";
var curriedSearchI = s => String.Compare(searchKey, s, StringComparison.InvariantCultureIgnoreCase)==0);

searchSomething(curriedSearchI);
// ....
bool searchSomething(Func func)
{
return someColl.Any(func);
}

Try implementing that without some form of currying....

And make sure your implementation also handles this:

var searchKey1 = "James";
var searchKey2 = "Curran";
var anotherSearchI = s => String.Compare(searchKey1, s, StringComparison.InvariantCultureIgnoreCase)== 0 && String.Compare(searchKey2, s, StringComparison.InvariantCultureIgnoreCase)== 0);

searchSomething(anotherSearchI);

Mike Hadlow said...

Thanks James, that's a great example.

Unknown said...

Really cool post. I was wondering if this was possible in C# today and google brought me here.

Unknown said...

What... had no idea! thanks!

Unknown said...

What... had no idea! Thanks!