Partial Function Application (Schönfinkelisation) in C#

That's right, I labeled partial function application Schönfinkelisation instead of Currying. Don't take that the wrong way, I'm extremely fascinated by Haskell Curry, but Moses Schönfinkel was responsible for the theory behind it. But I do have to be fair. While Schönfinkel developed and wrote about the technique, it was Curry who used it to simplify the lambda calculus. Then as this technique bled into functional programming and became a topic found in any CS curriculum, it did make some sense to name if after the individual who made it popular in practice.

Although Schönfinkelisation does sound quite a bit nerdier, using that term in casual conversation has the same result on the opposite sex as the Axe Effect. Trust me. But for the sake of keystrokes and eye spasms, I'll use the term Curry instead of Schönfinkelize.

So what is partial function application anyway? Partial function application is the technique of taking a function which takes n arguments and turning it into a function which takes 1 argument and returns a function which takes n-1 arguments. In other words, this technique involves fixing arguments in function bodies. The whole idea here is to incrementally apply arguments to functions. That is an odd statement, how can you possibly call a function without supplying all of that functions arguments? That is what we'll soon find out.

How then did H. Curry used this technique to simplify the lambda calculus? The same way you would simplify juggling 2 balls by fixing the second ball inside of the first and then just throwing the first ball up and down in the air. Lets see how this would look in some code:

void Juggle(Ball i, Ball j)
{
    _ball1 = i;
    _ball2 = j;
    .......
}

There's not a lot happening there, but its not the implementation we care about, its about currying. So we have a function that takes 2 arguments. If we are to curry this function, we fix one of the arguments in our function body so that it only takes 1 argument. Note: this isn't currying as per the definition of the technique, this is just an example to illustrate my juggling example.

void Juggle(Ball j)
{
    _ball1 = some_previously_set_value;
    _ball2 = j;
    ........
}

I know that's not the least bit exciting, so how about a real example? Lets define a function that tests the equality of two strings:

Func<string, string, bool> isSame = (a, b) => a.Equals(b);

Here we have a function isSame that takes two string arguments and returns a boolean indicating if they are the same or different. If we try and follow our definition of currying, we need to transform this function into one that takes only one argument and returns a function which takes one argument and returns a boolean. For this, we will define a function called Curry to help us do just that. What Curry will do is take the arguments to isSame, and fix them in such a way that isSame will not get called until both arguments have been fixed. Here is what Curry looks like:

static Func<X, Func<Y, Z>> Curry<X, Y, Z>(this Func<X, Y, Z> f)
{
    return x => y => f(x, y);
}

I first learned this technique in college and have to admit that when I first looked at what currying does, it took me a bit to fully "get it". But there really isn't much to it, there's no magic here, just types. So let's pay attention to the types and go through an example of how this works. From the body of Curry you can see that it takes one argument (x) and returns a function (y => f(x, y)). When you give Curry the first argument, it gets plumbed into the function which it returns. Let's give Curry's body an argument of "string1":

return x => y => f(x, y);

becomes

return y => f("string1", y);

When we apply one argument to Curry, it returns a function with that argument inserted into the body for each instance of the argument name. Let's replace our first generic type parameter with string and see if our types match:

static Func<string, Func<Y, Z>> Curry<Y, Z>(this Func<string, Y, Z> f)
{
    return x => y => f(x, y);
}

Notice that we've replaced our generic type parameter "X" with string and have removed the generic type from our definition of Curry. Now we should be able to plumb in "string1" as our first parameter. Let see what that looks like:

static Func<Y, Z> Curry<Y, Z>(this Func<string, Y, Z> f)
{
    return y => f("string1", y);
}

What we've essentially done here is Curry our isSame function by fixing the value "string1" for the argument "X". We've turned isSame into a function that takes 1 argument and returns a function that accepts 1 argument and returns a bool. Think of isSame as now looking like this:

Func<string, bool> isSame = b => "string1".Equals(b);

At this point it might make more sense to think of isSame as isSameAsstring1 since we've removed its flexibility by fixing its first argument in its body. To Curry a function, we don't actually create a function called Curry with arguments fixed in its body, I only did that for the sake of an explanation. We would actually want to pass our function to Curry and then apply arguments to our new Curried function. So lets create a new function called isSameAsstring1 by currying our isSame function and fixing the value "string1" in for the first argument:

Func<string, Func<string, bool>> isSameCurried = isSame.Curry();
Func<string, bool> isSameAsstring1 = isSameCurried("string1");

We've created a function called isSameCurried by passing our isSame function into our Curry function. What this allows us to do is create a function with a fixed argument that returns a function which executes isSame on that fixed argument. Which is what the second line does. Our function isSameAsstring1 is the isSame function with a fixed argument of "string1". Voila, that's almost Currying. I say almost because we don't actually have to create a curried function (isSameCurried above) in order to fix an argument in our target function. If we re-work our Curry function a bit, we should be able to provide the ability to fix an argument up front:

static Func<Y, Z> Curry<X, Y, Z>(this Func<X, Y, Z> f, X x)
{
    return y => f(x, y);
}

Which we can then call like this:

Func<string, bool> isSameAsstring1 = isSame.Curry("string1");

None of these examples have been very practical, but they have demonstrated a very powerful technique. Let's assume a hypothetical situation where we have some text in which we have to write out to a file, but (for some odd reason) we don't know the destination at the time in which we know the contents of the file to be created. We could create a helper class with properties describing the file name, contents and destination directory which we could use to create the file once we have all the data we need. But let's try creating a function that takes some data to write to a file and the destination as arguments and curry this function. We'll start with a delegate which points to a helper function which writes some string data out to a text file:

Func<string, string, FileInfo> CreateFile = CreateFileHelper;
.......
FileInfo CreateFileHelper(string destination, string data)
{
    FileInfo fi = new FileInfo(destination);
    if (!fi.Exists())
    {
        using (StreamWriter sw = fi.CreateText())
        {
            sw.Write(data);
        }
    }
    return fi;
}

Nothing fancy here, just created a delegate which points to our helper. So now, let's Curry our helper method by fixing the destination and in the process creating a new function which is able to write data out to a specific file:

Func<string, FileInfo> CreateFileOnC = CreateFile.Curry(@"C:\NewFile.txt");

CreateFileOnC represents the CreateFile method with its destination argument fixed. Now at some later point in our program where we have data to write to this directory, we can just apply that data to our Curried CreateFile method:

FileInfo fi = CreateFileOnC("hello world!");

This approach to customizing methods allows us to create generic (not in the type sense) functions which we can customize for specific needs at run time. Pretty neat.

On a side note, this technique wouldn't be possible without the support of Closures in C# 3.0. A discussion on Closures is out of the scope of this post, but it does provide me with a perfect segue into my next post. Come back soon and I'll tackle Closures and why you need to know about them.