Currying

In this post we will talk about currying, why you may need it, how to implement it with different paradigms (OOP, meta-programming, and functional).

Let's first talk about motivation. Consider the simple scenario where you have a list of integers, and you want to filter it to extract only the integers you want. For instance this list could be a list of user IDs, and you want to extract only the users who are late in their payments to send them an email. 

It is pretty much straight forward to do it in a loop; but we want a clearer way that focuses on semantics. For example consider something like 

send_email_to(select_from(all_users, payment_due))

I've colored payment_due in red to make it clear its a function, not a variable. The function select_from could contain the loop structure (and maybe some database processing), where in each loop they apply the function payment_due to some user like this:

select_from(list, test)

{

  selected = {};

  for(i=0; i < list.length; i++)

    if(test(list[i]) == true)

      append(selected,list[i])

  return selected;

}

Notice that the function payment_due must be a function that takes only one parameter, because that is how it will be called from inside select_from. In most languages which have first-class functions there is a built-in function which acts like select_from, exactly for this kind of purpose. This includes C++ and all functional programming languages. In C++11 it is called copy_if (it was dropped from C++ by accident).

Consider another «test» function that takes as argument a user ID, and returns true if the user’s monthly salary is more than 3000. That could be written as:

salary_greater_than_3000(user)

{

   return user.salary > 3000;

}

send_email_to(select_from(all_users, salary_greater_than_3000))

Maybe we have something like this:

salary_greater_than_x(user,x)

{

   return user.salary > x;

}

salary_greater_than_3000(user)

{

   return salary_greater_than_x(user,3000);

}

send_email_to(select_from(all_users, salary_greater_than_3000))

C++ macros won’t do the same thing as above, but C++ STL bind2nd (which is also compile-time meta-programming) can do the same thing.

If we don’t know the value 3000 at compile time and instead we only have it in run-time, we can’t do this call select_from(all_users, salary_greater_than_x). This wouldn’t work because select_from expects a function taking one parameter only.

In C++ this could be fixed by using a functor, which is a class which overrides operator(), and hence could be used as a function. For example (this example is valid C++, not just pseudo code as the previous examples):

class salary_greater_than_x

{

   const int x;

   public: salary_greater_than_x(int x): x(x){}

   bool operator()(User user) { return user.salary() > x; }

}

send_email_to(select_from(all_users, salary_greater_than_x(3000)))

Lambda expressions does the same thing exactly, without the need to write a class for it. In C++11 (which supports lambda epxressions) that would be like:

send_email_to(select_from(all_users, [](User user){salary_greater_than_x(user,3000)}))

The lambda expression, just like the functor, stores the value 3000, which is a sort of a closure.

Lambda expressions is too powerful; you can define arbitrary functions. We don’t need all that power, we only need to fix one argument of another function. This is what currying does. For instance, we know that salary_greater_than_x takes two arguments. If the language we are using supports implicit currying (like Haskell) if we omitted the second parameter we end up with a function whose first parameter is fixed. Concretely speaking we can do this (notice I switched the first and second parameters in the definition of salary_greater_than_x) :

salary_greater_than_x(x, user)

{

   return user.salary > x;

}

salary_greater_than_3000 = salary_greater_than_x(3000)

send_email_to(select_from(all_users, salary_greater_than_3000))

or simply just :

send_email_to(select_from(all_users, salary_greater_than_x(3000)))