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)))
