次の方法で共有

Currying and Partial Function Application

  • [アーティクル]

When I first heard the term Currying, I thought immediately of tasty Thai and Indian food.  To my dismay, I found that the conversation was not about wonderful spices but rather about transforming a function that takes n arguments into a function that takes only one argument and returns a curried function of n - 1 arguments.  Why in the world would that be useful?

From a theoretical standpoint, it is interesting because it simplifies the lambda calculus to include only those functions which have at most one argument.  From a practical perspective, it allows a programmer to generate families of functions from a base function by fixing the first k arguments.  It is akin to pinning up something on the wall that requires two pins.  Before being pinned, the object is free to move anywhere on the surface; however, when when first pin is put in then the movement is constrained.  Finally, when the second pin is put in then there is no longer any freedom of movement.  Similarly, when a programmer curries a function of two arguments and applies it to the first argument then the functionality is limited by one dimension.  Finally, when he applies the new function to the second argument then a particular value is computed.

What this means in C# is if I have a delegate which is of type Func<A,B,R> (delegate with two arguments of type A and B respectively and returns type R) then I can create a delegate which is of type Func<A,Func<B,R>>.  Notice how the curried delegate only has one argument but it returns a delegate which takes the original function's second argument and finally returns a value.

Consider generating functions from the add function.

Func<int,int,int> add = (x,y) => x + y;

We can curry add by applying the Curry function to add.

Func<int,Func<int,int>> curriedAdd = add.Curry();

This curried add function is really a function that creates functions that add n where n is the argument to the curried add function.  For example, we can create an increment function by applying the curried add function to the value one.

Func<int,int> inc = curriedAdd(1);

The increment function will now return one plus the value of its argument when invoked.  We can now use our three functions to do various forms of addition.

Console.WriteLine(add(3,4)); // 7
Console.WriteLine(curriedAdd(3)(5)); // 8
Console.WriteLine(inc(2)); // 3

So how would this function Curry look?  It's really pretty simple.

public static Func<A, Func<B, R>> Curry<A, B, R>(this Func<A, B, R> f)
{
return a => b => f(a, b);
}

It just takes a function of two arguments and then returns a lambda which fixes the first argument and then the second argument.  Once both arguments have been provided it evaluates the original function with the arguments.  It is easy to follow the same pattern and create a function Curry which curries a functions of other arities.

Let's examine what went on when we created each of the functions.  First we created a function called add which looked like:

(x, y) => x + y

 Once we curried add, the function became:

x => y => x + y

We created inc by calling curried add with the value 1.  This essentially created the following function:

y => 1 + y

The idea of currying a function and then fixing the first n arguments of the original function can be generalized into an concept called partial function application.  For instance, if we consider our add function from the previous example then we can directly create the increment from add without having to create curriedAdd first.

Func<int,int> inc = add.Partial(1);

Where the Partial function is written as:

public static Func<B, R> Partial<A, B, R>(this Func<A, B, R> f, A a)
{
return b => f(a, b);
}

Notice how the function takes a function and a value which has the same type as the first argument of the function.  It then returns a function which takes the remaining arguments and then applies all of the arguments to the original function.  This can be generalized into a set of functions that produce partially applied functions.

Comments

  • Anonymous
    February 01, 2007
    Welcome to the twentieth Community Convergence. I'm Charlie Calvert, the C# Community PM, and this is

  • Anonymous
    February 01, 2007
    Welcome to the twentieth Community Convergence. I'm Charlie Calvert, the C# Community PM, and this is

  • Anonymous
    February 02, 2007
    Recursion is beautiful and lambdas are the ultimate abstraction. But how can they be used together? Lambdas

  • Anonymous
    January 31, 2010
    This is very cool. It's unfortunate that, as far as I can tell, there is no way to do something equivalent for class methods without converting them to Funcs. For example, it would be convenient to have this work: class MyType {    public int State { get; set; }    public int Add(int x) { return State + x; } } // f.GetType() == typeof(Func<MyType, int>) var f = MyType.Add.Curry(1); var mt = new MyType() { State = 2 }; Console.WriteLine(f(mt));     // prints 3 // f2.GetType() == typeof(Func<int>) var f2 = mt.Add.Curry(3); Console.WriteLine(f2());      // prints 5 If you have to rewrite the Add method as a lambda before you can curry, it seems like you lose a lot of the syntactic converience of a generic curry function. Maybe in C# 5 :(