Curry vs Partial function application

Translation of the article by John Skit, the well-known guru of C # , author of C # In Depth, Google employee, person # 1 on reputation on stackoverflow.com and finally the hero Jon Skeet Facts . In this article, John explains in an accessible way what the currying and partial application of a function are, concepts that come from the world of functional programming. In addition, he explains in detail what is their difference. I confess that I myself confused them before reading this article, so it seemed to me useful to make a translation.


This is a bit of a strange post, and before reading it you probably should consider yourself as one of these groups:

• Those who are not interested in functional programming and find the higher-order functions confusing: you can skip this article completely.
• Those who know all about functional programming and understand the difference between currying and partial function application: please read this post carefully and write in the comments if you find inaccuracies.
• Those who are partly familiar with functional programming and are interested in learning more: be skeptical and read the comments carefully in this post. Read other articles by more experienced developers for more information.

In general, I know that some people sometimes confuse the terms currying and partial use of a function — they are used interchangeably when they should not be done. This is one of those topics (such as monads), which I understand to some extent, and I decided that the best way to verify my knowledge would be to write about it. If it makes this theme more accessible to other developers, so much the better.

')

This post does not contain Haskell

In almost all the explanations on this topic that I saw, examples were given in “correct” functional languages, usually in Haskell. I have nothing against Haskell, it's just usually easier for me to understand examples in a language I know well. Moreover, it is much easier for me to write examples in such a language, so all the examples in this post will be in C #. Actually, all the examples are available in one file , although several variables in it are renamed. Just compile and run.

C # is not really a functional language — I know enough to understand that delegates are not a complete replacement for higher order functions. Nevertheless, they are good enough to demonstrate the principles described.

Although it is possible to demonstrate currying and partial application using a function (method) with a small number of arguments, I decided to use three arguments for clarity. Although my methods of performing currying and partial application will be generalized (therefore, all types of parameters and return value are arbitrary), for the purpose of demonstration I use a simple function:

static string SampleFunction(int a, int b, int c) { return string.Format("a={0}; b={1}; c={2}", a, b, c); } 

So far, everything is simple. There is nothing tricky in this method, do not look for anything surprising in it.

What is it all about?

Both currying and partial application are ways to convert one kind of function into another. We will use delegates as an approximation of functions, so to work with the SampleFunction method as a value, we can write:

 Func<int, int, int, string> function = SampleFunction; 

This line is useful for two reasons:

• Assigning a value to a variable suggests the idea that it really is a value. A delegate instance is an object, just like any other type of instance, and the value of a function variable is just a reference.
• Converting a group of methods (using the method name as a way to create a delegate) does not work well with type inference when a generic method is called.

Now we can call the delegate with three arguments:

 string result = function(1, 2, 3); 

Or the same:

 string result = function.Invoke(1, 2, 3); 

(The C # compiler converts the first short form to the second. The generated IL will be the same.)

It is good if all three arguments are available to us at the same time, but what if not? For a specific (albeit somewhat contrived) example, suppose we have a logging function with three parameters (source, severity, message) and within the same class (which I will call BusinessLogic), we want to always use the same value for the parameter "a source". We want to be able to easily log from any point of the class, indicating only the seriousness and the message. We have several options:

• Create an adapter class that accepts a logging function (or even a logger object) and the value of the “source” parameter in its constructor, stores them in its fields and exposes a method with two parameters. This method simply delegates the call to the stored logger, passing the saved “source” to the first parameter of the logger function. In the BusinessLogic class, we create an adapter instance and store a reference to it in the field, and then simply call the method with two parameters where we want. This is probably an overkill if we need only an adapter from BusinessLogic, but it can be reused ... as long as we adapt the same logging function.
• Store the original logger object in our BusinessLogic class, but create an auxiliary method with two parameters, inside which the value for the “source” parameter will be hard coded. If we have to do this in several places, it becomes annoying.
• Use a more functional approach - in this case, a partial application of the function .

I deliberately ignore the difference between storing a link to a logger object and storing a link to a logging function. Obviously, there is a significant difference if we need to use more than one function of the logger class, but in order to reflect on the currying and partial application, we will think of the “logger” as a “function that takes three parameters” (like our function in the example ).

Now that I have given a pseudo-real concrete case for motivation, we will forget it until the end of the article and we will consider only an example function. I don’t want to write an entire BusinessLogic class that will pretend to be doing something useful; I am sure you can make a mental transformation from an “example function” to “something that you really would like to do.”

Partial application of the function

Partial application takes a function with N parameters and a value for one of these parameters and returns a function with N-1 parameters, such that, when called, it will collect all the necessary values ​​(the first argument passed to the function of the partial application and the rest N-1 arguments passed to the return function). Thus, these two calls must be equivalent to our method with three parameters:

 //   string result1 = function(1, 2, 3); //     Func<int, int, string> partialFunction = ApplyPartial(function, 1); string result2 = partialFunction(2, 3); 

In this case, I implemented a partial application with a single parameter, the first in a row — you can write ApplyPartial, which will take more arguments or substitute them in different positions in the final execution of the function. Apparently, collecting parameters one by one, starting from the beginning is the most common approach.

Thanks to the anonymous functions (in this case, the lambda expression, but the anonymous method would not be much more verbose), the ApplyPartial implementation is simple:

 static Func<T2, T3, TResult> ApplyPartial<T1, T2, T3, TResult> (Func<T1, T2, T3, TResult> function, T1 arg1) { return (b, c) => function(arg1, b, c); } 

Generalizations make this method look more complicated than it really is. Note that the lack of higher order types in C # means that you need to implement this method for each delegate you want to use — if you need a version for a function with four parameters, you need the ApplyPartial <T1, T2 method , T3, T4, TResult>, etc. You will probably also need a set of methods for the Action delegate family.

The last thing to note is that with all of these methods, we can perform partial applications again, even potentially up to the resulting function without parameters, if we want:

 Func<int, int, string> partial1 = ApplyPartial(function, 1); Func<int, string> partial2 = ApplyPartial(partial1, 2); Func<string> partial3 = ApplyPartial(partial2, 3); string result = partial3(); 

Again, only the last line will call the original function.

Ok, this is a partial application of the function. It is relatively simple. Carring, in my opinion, is a bit more difficult to understand.

Carring

While a partial application converts a function with N parameters into a function with N-1 parameters, applying one argument, currying decomposes the function into functions from one argument. We do not pass any additional arguments to the Curry method, except for the function being transformed:

• Curry (f) returns a function f1, such that ...
• f1 (a) returns the function f2, such that ...
• f2 (b) returns a function f3, such that ...
• f3 (c) causes f (a, b, c)

(Again, note that this only applies to our function with three parameters — I hope, obviously, this will work with other signatures.)

For our “equivalent” example, we can write:

 //   string result1 = function(1, 2, 3); //    Func<int, Func<int, Func<int, string>>> f1 = Curry(function); Func<int, Func<int, string>> f2 = f1(1); Func<int, string> f3 = f2(2); string result2 = f3(3); //     ... var curried = Curry(function); string result3 = curried(1)(2)(3); 

The difference between the last examples shows the reason why functional languages ​​often have good type inference and a compact representation of function types: the f1 declaration is very scary.

Now that we know what the Curry method should do, its implementation is surprisingly simple. In fact, all we need to do is translate the points above into lambda expressions. Beauty:

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

Feel free to add parentheses if you want to make the code more understandable to you; I personally think that they will only add confusion. In any case, we got what we wanted. (It is worth thinking about how tedious it would be to write without lambda expressions or anonymous methods. Not difficult , just tiring.)

This is the curry. I think. Maybe.

Conclusion

I cannot say that I have ever used currying, whereas some parts of text parsing for Noda Time actually use partial application. (If someone really wants me to check it, I'll do it.)

I really hope that I showed you the difference between these two interrelated, but nonetheless very different concepts. Now that we’ve come to an end, think about how the difference between them will manifest for a function with two parameters, and I hope you will understand why I decided to use three :)

My sixth sense tells me that currying is a useful concept in an academic context, while partial application is more useful in practice. However, this is the sixth sense of a person who did not use the functional languages ​​to the fullest. If I ever start using F #, maybe I will write a complementary post. Now, I hope that my experienced readers can give useful thoughts in the comments.