Partial use and currying in C ++

Greetings.

I don’t know how it happened, but I played at leisure with lambda expressions in C ++ 11 (which, by the way, I already wrote an article that gained surprisingly quite good popularity a couple of years ago), and under the influence of drugs I was impressed Haskell began to understand concepts such as partial use and currying in the context of C ++. And for starters, perhaps it would be nice for us to define these terms.

Actually, a partial use of a function is the ability to fix a certain value for one of the parameters of the function, that is, from the function of N parameters we get a function of N-1 parameters. If we have a binary function that sums two numbers:
int sum(int a, int b) { return a + b; }

then we can fix a certain value for one of the parameters, for example, 42. Thus, we get a new, already unary function, adding the number 42 to its argument.
Strictly speaking, partial application of functions was in the previous C ++ standard. This role was performed by two classes std::binder1st and std::binder2nd , as well as by all known auxiliary functions std::bind1st and std::bind2nd which simplify the creation of objects of the above classes. True, there is one problem: these binders cannot work with ordinary function pointers, because they need to know the type of parameters. To solve this and other problems, STLs use functors everywhere. To be honest, I would prefer to call them functional objects, because From the time I met Haskell, the word "functor" has been associated with a completely different essence. However, in the circles of C ++ programmers, this term has been fixed precisely for the designation of objects that can behave like functions; moreover, it’s faster to write :)
So how is this problem solved? If someone does not know, I will tell in a nutshell. Classes std::binder1st and std::binder2nd , which by the way work only with binary functions, require several typedef in the functor you define: these are result_type, first_argument_type and second_argument_type. In order to not have to declare these types manually in your functor each time, you can simply inherit from std::binary_function<T0,T1,R> , where T0 and T1 are the types of function arguments, and R is the type of the return value, respectively.

An example of using this whole thing is something like this:


template <typename T>
struct Sum
	: public std::binary_function<T, T, T>
{
	T operator()(T const & a, T const & b)
	{
		return a + b;
	}
};

// а затем

std::for_each(intArray.begin(), intArray.end(), std::bind1st(Sum<int>(), 42));


Those constructs who have been familiar with STL for a long time are no longer afraid of such constructions (and I, unfortunately, are among them), but believe me, piling up all these special characters and wrappers frightens newcomers who came to C ++ from other languages. It’s better not to remember about readability either, because I have seen combinations better than this :) Especially since later in Boost library a more powerful replacement appeared - Boost.Bind, which, however, differed even less in readability (typical C ++ - way) . By the way, it should be noted that Boost.Bind migrated to the new C ++ 11 standard to replace the old binders, which I talked about a bit above. However, who will use it when there is ... what? That's right, lambdas! Well, with them, it’s a completely different matter :) The writings are less, the readability is better (compared to binders, of course, and not with other languages;)).

So, we have a functor Sum , which we defined above. Я может забыл сказать, но в STL и так уже есть подобный функтор — std::plus<>. But we can do without it, since we wrote our own similar one. In general, we have a binary functor, and we need to get a partially applied unary. With lambdas, it might look like this:


using namespace std; // для for_each, begin и end
// ...
Sum<int> sum;
for_each(begin(intArray)), end(intArray), [sum] (int const & n)
{
	return sum(42, n);
});


You may ask why we are calling here sum(42, n) when we can write directly in the body of a lambda return 42 + n; . The observation, of course, is true, but we are interested in the partial application of the function, if you have not forgotten yet. In addition, the function could be much more complicated than simply adding up two numbers.

And how would we write it in Haskell? Perhaps, something like this would turn out:
sum a b = a + b

someFunc intList = map (λ n → sum 42 n) intList


If you are not familiar with Haskell, do not despair. This code is similar to the last example in C ++. Now I’ll explain in a nutshell: in the first line, we announced a function sum that takes a and b returns their sum. Next, we announced some function that takes some list as a parameter (probably a list of integers, judging by the name of the parameter) and does something with it. A function map is an analog std::for_each , i.e. it takes some function and calls it for each element of the list. As a function, we pass a lambda that calls the function sum , explicitly passing it a fixed value as the first parameter, and the lambda argument naturally acts as the second parameter. All this is really not important ... Or rather, it could have been not important if the same Haskell code could not be written like this:

sum a b = a + b

someFunc intList = map (sum 42) intList


As we can see, this time instead of the lambda we used a much shorter construction, namely the call of a binary function sum with one parameter. How does it work? Yes, very easy! :) The call (sum 42) will return a new function to us, which takes one parameter, and then sums it up with the number 42. In fact, this is the same partial application - we just say the function sum : “Here is the first parameter for you, remember it! But we still do not know the second parameter, so you have to deal with it later. ” All this works due to the fact that all functions in Haskell are curried (by the way, there was such a mathematician - Haskell Curry;)). So it's time to figure out what it is.

First, currying is an operation. That is, it’s not just some property or magical creature in the Haskell universe, it’s a transformation. Secondly, this is a conversion performed on a function: it takes a function of N parameters and converts it to a similar function of one parameter, which returns a function of N-1 parameters. I will explain with an example. To do this, let's return to our C ++ function sum , but add one more parameter to it (just in case):
template <typename T1, typename T2, typename T3, typename R>
R sum(T1 a, T2 b, T3 c) { return a + b + c; }

Since we are only interested in the types of parameters and return value, we will write its type as follows:
sum :: ((T1 × T2 × T3) → R)

This record means that the function takes three arguments of types T1, T2 and T3, respectively, and returns a value of type R. Actually, after currying, by definition above, we should get something like this:
sum :: (T1 → ((T2 × T3) → R))

That is, it is a function that takes one parameter of type T1, and returns another function, which in turn takes two arguments of types T2 and T3, respectively, and returns (as before) a value of type R. In fact, we “bite off” the first parameter of the function and say, they say, "we remember him, do not worry." And then we return a similar function that takes one parameter less. Doesn’t resemble anything? But on the basis of this, partial application can be realized!

But ... in fact, I was a little cunning. If everything worked this way, then we would have to curry the resulting function after partially applying each successive function argument. Judge for yourselves: we have a ternary function, which we curry and get a unary function. To this unary function, we pass its only parameter and as a result we get another binary function. Now, if we want to perform a partial application for another parameter, we will again have to perform currying, only now for a binary function. It makes no sense to fool yourself with this every time, so in fact, as a result of currying, we get the following:
sum :: (T1 → (T2 → (T3 → R)))

In essence, this is the same, only instead of returning a binary function, we return it immediately as curried. Thus, from the multi-input function we got a unary chain, which, firstly, allows us to partially apply the arguments in order, and secondly, when applying all the arguments, it will behave equivalently to the original function, that is, it will give the same output result .

I hope so far everything has been more or less clear. But, I think, many of you are already pointing a finger at the monitor with an exclamation: “Well, finally show me the bljad code!” Reasonably, I can not object. Therefore, with the theory finished, we turn to practice. It's 2012, so we will use the new C ++ 11 standard, although we will try to limit ourselves only to what Microsoft Visual Studio 2010 supports - in terms of supporting the new standard, it is probably the most lagging release compiler.

Let's start with a simple one. There is a binary function. As a result of currying, we should get a unary function that returns us another unary function. Using C ++ 11, this is easier than steamed turnip:

#include <cstddef>
#include <iostream>

using namespace std;

template <typename R, typename T0, typename T1>
function<function<R(T1)>(T0)> curry_(function<R(T0,T1)> f)
{
    return [=] (T0 const & t0) -> function<R(T1)>
    {
        return [=] (T1 const & t1) { return f(t0, t1); };
    };
}

int sum(int a, int b) { return a + b; }

int main()
{
	auto curried_sum = curry_<int,int,int>(sum);

	cout << sum(42, 10)         << endl;   // => 52
	cout << curried_sum(42)(10) << endl;   // => 52

	return EXIT_SUCCESS;
}


In general, there are such things: our function curry_ depends on three template parameters (types of function arguments and return type). It takes an object of type as an argument std::function<> . If anyone does not know, this is such a universal container that can store functors, lambdas, and even function pointers (Yay! No more bunts :)). It is important for us that in fact it is a functional object, that is, it is overloaded operator() . Next, we simply return the unary lambda (essentially an anonymous functor), which returns another unary lambda. This is almost one in one translation of the definition of the term currying from Russian to C ++.

Now an important moment has come. Everyone who has read to this place should ask their inner voice which option they like best:


std::bind1st(std::function<int(int,int)>(sum), 42)(10);
// или 
curry_<int,int,int>(sum)(42)(10);


If the first, you can no longer read, believe me. If the second one, then I must admit to you ... I myself don’t quite like the second option, although in my opinion it is already much better than the first.

One way or another, I'm a little annoyed by the need to explicitly specify the types of arguments and return value. The compiler cannot automatically output all types on its own, so it has to be prompted. In addition, if we want to overload the function curry_ for the ternary function, we will fail because the compiler cannot distinguish between instances std::function<> . As I understand it, the reason for this is std::function<> a template constructor is defined that accepts any type, but we won’t go into it now, because I'm not completely sure that I understood the problem correctly. However, the fact remains. And you need to do something about it.

The question with the need to indicate the types of arguments and return value will be tried to solve as follows. We curry_ leave the function curry_ as it is, and for it we write a template wrapper, which we will accept as a template parameter of any type. Next, we will write something like function_traits (by the way, it’s strange that this is not in the standard, isn’t it?), In which we will remember the types of arguments, etc. The approach to writing the so-called traits classes is commonly used in the STL, so why not do this to us.


template <typename Func>
struct function_traits {};

// специализация шаблона для бинарных функций
template <typename R, typename T0, typename T1>
struct function_traits<R(*)(T0,T1)>
{
	typedef R  result_type;
	typedef T0 first_argument_type;
	typedef T1 second_argument_type; 
};

// обёртка для curry_
template <typename Functor>
function<
    function<
        typename function_traits<Functor>::result_type(typename function_traits<Functor>::second_argument_type)
    >(typename function_traits<Functor>::first_argument_type)
>
    curry(Functor f)
{
    return curry_
            < typename function_traits<Functor>::result_type
            , typename function_traits<Functor>::first_argument_type
            , typename function_traits<Functor>::second_argument_type
            > (f);
}


Well, just two dozen lines of not very readable code, and we can already write like this:

cout << curry(sum)(42)(10) << endl;


In my opinion, this is a success! :) It remains to implement curry_ for ternary functions, and even so that we do not have to get another function name for these purposes - let everything be solved by overloading the functions. So far, my instinct tells me that this will be problematic. Look at least at the wrapper function curry : it takes only one parameter (directly the function to be curried), but it should always return objects of different types depending on the arity of the function (i.e. it will return a function that returns a function, or a function that returns a function that returns a function, or ... mmm, that's enough).

To solve this problem, you will have to bend a little metaprogramming think and find inspiration. So, for starters, we need to distinguish between unary, binary, ternary, ... n-ary functions. I think for this you can add a function_traits static constant that will be initialized with a different value depending on the specialization of the template. Next, we will add curry an additional dummy argument to our wrapper function , which will only take part in resolving function overloads at the compilation stage.

We get the following:

template <typename Func>
struct function_traits {};

// специализация шаблона для унарных функций
template <typename R, typename T0>
struct function_traits<R(*)(T0)>
{ 
	typedef R  result_type; 
	typedef T0 argument_type; 
	static const int arity = 1; 
};
 
// специализация шаблона для бинарных функций
template <typename R, typename T0, typename T1>
struct function_traits<R(*)(T0,T1)>
{
	typedef R  result_type;
	typedef T0 first_argument_type;
	typedef T1 second_argument_type; 
	static const int arity = 2;
};

// специализация шаблона для тернарных 
template <typename R, typename T0, typename T1, typename T2>
struct function_traits<R(*)(T0,T1,T2)>
{
	typedef R  result_type; 
	typedef T0 first_argument_type; 
	typedef T1 second_argument_type; 
	typedef T2 third_argument_type; 
	static const int arity = 3; 
};

// метафункция для подсчёта аргументов
template<typename Functor, int NArgs>
struct count_args
    : std::enable_if<function_traits<Functor>::arity == NArgs>
{ static_assert(NArgs >= 0, "Negative number? WTF?"); };


// обёрки

// для унарной функции каррирование не имеет смысла, поэтому возвращаем исходную функцию
template <typename Functor>
Functor curry(Functor f, typename count_args<Functor, 1>::type * = 0)
{
    return f;
}

// бинарная функция
template <typename Functor>
std::function<
    std::function<
        typename function_traits<Functor>::result_type(typename function_traits<Functor>::second_argument_type)
    >(typename function_traits<Functor>::first_argument_type)
>
    curry(Functor f, typename count_args<Functor, 2>::type * = 0)
{
    return curry_
            < typename function_traits<Functor>::result_type
            , typename function_traits<Functor>::first_argument_type
            , typename function_traits<Functor>::second_argument_type
            > (f);
}

// тернарная функция
template <typename Functor>
std::function<
    std::function<
        std::function<
            typename function_traits<Functor>::result_type(typename function_traits<Functor>::third_argument_type)
        >(typename function_traits<Functor>::second_argument_type)
    >(typename function_traits<Functor>::first_argument_type)
>
    curry(Functor f, typename count_args<Functor, 3>::type * = 0)
{
    return curry_
            < typename function_traits<Functor>::result_type
            , typename function_traits<Functor>::first_argument_type
            , typename function_traits<Functor>::second_argument_type
            , typename function_traits<Functor>::third_argument_type
            > (f);
}


In general, everything is very clear here. We implemented function overloading by adding a second dummy parameter. This parameter is used std::enable_if to "turn off" inappropriate function options curry during the resolution of overload. We also added a curry implementation for unary functions that simply returns the original function. It remains to write an implementation for the function curry_ for ternary functions. In the theoretical part, I mentioned that during the currying of a ternary function, the result will be unary, which could theoretically return a function of two arguments, but actually returns its curried version. With this knowledge, the implementation for the three arguments is extremely simple:

<typename R, typename T0, typename T1, typename T2>
function<function<function<R(T2)>(T1)>(T0)> curry_(function<R(T0,T1,T2)> f)
{
    return [=] (T0 const & t0) -> function<function<R(T2)>(T1)>
    {
        return curry_<R,T1,T2>([=] (T1 const & t1, T2 const & t2)
        {
            return f(t0,t1,t2);
        });
    };
}

In general, I wrapped all this (except for examples of use, of course) in a namespace mega and added specializations function_traits for functors, stuffed it into one header file and uploaded it to GitHub . It will be necessary to add README somehow :) Now we can write any nonsense using ternary functions. Yes, even like this:

string foo(string s, int i, double d)
{
    ostringstream str;
    str << s << ": " << i << " л. = " << d << "$";
    return str.str();
}

int main()
{
    cout << mega::curry(foo)("Кока-кола")(2)(9.95) << endl;  // => Кока-кола: 2 л. = 9.95$

    return EXIT_SUCCESS;
}


The whole charm of this approach is that new, more specific functions can be built on the fly from the "wider" ones. How and where exactly this can be applied, everyone will decide for himself.

Honestly, I did not check whether something similar had already been implemented, so I do not exclude that I wrote another bike, because it was interesting to me from an academic point of view. In addition, from the point of view of optimality, I also did not go into much detail so far. I can immediately say that the C ++ compiler doesn’t optimize such things, so as a result we get a whole bunch of call 's with dragging different information between registers. But you have to pay for convenience.

Thanks for your attention.

May the Force be with you.

P.S. У меня сейчас раннее утро, а онлайн я появлюсь скорее всего ближе к вечеру. So don’t do much without me :)