How can currying be done in C++?
Solution 1
In short, currying takes a function f(x, y)
and given a fixed Y
, gives a new function g(x)
where
g(x) == f(x, Y)
This new function may be called in situations where only one argument is supplied, and passes the call on to the original f
function with the fixed Y
argument.
The binders in the STL allow you to do this for C++ functions. For example:
#include <functional>
#include <iostream>
#include <vector>
using namespace std;
// declare a binary function object
class adder: public binary_function<int, int, int> {
public:
int operator()(int x, int y) const
{
return x + y;
}
};
int main()
{
// initialise some sample data
vector<int> a, b;
a.push_back(1);
a.push_back(2);
a.push_back(3);
// here we declare a function object f and try it out
adder f;
cout << "f(2, 3) = " << f(2, 3) << endl;
// transform() expects a function with one argument, so we use
// bind2nd to make a new function based on f, that takes one
// argument and adds 5 to it
transform(a.begin(), a.end(), back_inserter(b), bind2nd(f, 5));
// output b to see what we got
cout << "b = [" << endl;
for (vector<int>::iterator i = b.begin(); i != b.end(); ++i) {
cout << " " << *i << endl;
}
cout << "]" << endl;
return 0;
}
Solution 2
1. What is currying?
Currying simply means a transformation of a function of several arguments to a function of a single argument. This is most easily illustrated using an example:
Take a function f
that accepts three arguments:
int
f(int a,std::string b,float c)
{
// do something with a, b, and c
return 0;
}
If we want to call f
, we have to provide all of its arguments f(1,"some string",19.7f)
.
Then a curried version of f
, let's call it curried_f=curry(f)
only expects a single argument, that corresponds to the first argument of f
, namely the argument a
. Additionally, f(1,"some string",19.7f)
can also be written using the curried version as curried_f(1)("some string")(19.7f)
. The return value of curried_f(1)
on the other hand is just another function, that handles the next argument of f
. In the end, we end up with a function or callable curried_f
that fulfills the following equality:
curried_f(first_arg)(second_arg)...(last_arg) == f(first_arg,second_arg,...,last_arg).
2. How can currying be achieved in C++?
The following is a little bit more complicated, but works very well for me (using c++11)... It also allows currying of arbitrary degree like so: auto curried=curry(f)(arg1)(arg2)(arg3)
and later auto result=curried(arg4)(arg5)
. Here it goes:
#include <functional>
namespace _dtl {
template <typename FUNCTION> struct
_curry;
// specialization for functions with a single argument
template <typename R,typename T> struct
_curry<std::function<R(T)>> {
using
type = std::function<R(T)>;
const type
result;
_curry(type fun) : result(fun) {}
};
// recursive specialization for functions with more arguments
template <typename R,typename T,typename...Ts> struct
_curry<std::function<R(T,Ts...)>> {
using
remaining_type = typename _curry<std::function<R(Ts...)> >::type;
using
type = std::function<remaining_type(T)>;
const type
result;
_curry(std::function<R(T,Ts...)> fun)
: result (
[=](const T& t) {
return _curry<std::function<R(Ts...)>>(
[=](const Ts&...ts){
return fun(t, ts...);
}
).result;
}
) {}
};
}
template <typename R,typename...Ts> auto
curry(const std::function<R(Ts...)> fun)
-> typename _dtl::_curry<std::function<R(Ts...)>>::type
{
return _dtl::_curry<std::function<R(Ts...)>>(fun).result;
}
template <typename R,typename...Ts> auto
curry(R(* const fun)(Ts...))
-> typename _dtl::_curry<std::function<R(Ts...)>>::type
{
return _dtl::_curry<std::function<R(Ts...)>>(fun).result;
}
#include <iostream>
void
f(std::string a,std::string b,std::string c)
{
std::cout << a << b << c;
}
int
main() {
curry(f)("Hello ")("functional ")("world!");
return 0;
}
OK, as Samer commented, I should add some explanations as to how this works. The actual implementation is done in the _dtl::_curry
, while the template functions curry
are only convenience wrappers. The implementation is recursive over the arguments of the std::function
template argument FUNCTION
.
For a function with only a single argument, the result is identical to the original function.
_curry(std::function<R(T,Ts...)> fun)
: result (
[=](const T& t) {
return _curry<std::function<R(Ts...)>>(
[=](const Ts&...ts){
return fun(t, ts...);
}
).result;
}
) {}
Here the tricky thing: For a function with more arguments, we return a lambda whose argument is bound to the first argument to the call to fun
. Finally, the remaining currying for the remaining N-1
arguments is delegated to the implementation of _curry<Ts...>
with one less template argument.
Update for c++14 / 17:
A new idea to approach the problem of currying just came to me... With the introduction of if constexpr
into c++17 (and with the help of void_t
to determine if a function is fully curried), things seem to get a lot easier:
template< class, class = std::void_t<> > struct
needs_unapply : std::true_type { };
template< class T > struct
needs_unapply<T, std::void_t<decltype(std::declval<T>()())>> : std::false_type { };
template <typename F> auto
curry(F&& f) {
/// Check if f() is a valid function call. If not we need
/// to curry at least one argument:
if constexpr (needs_unapply<decltype(f)>::value) {
return [=](auto&& x) {
return curry(
[=](auto&&...xs) -> decltype(f(x,xs...)) {
return f(x,xs...);
}
);
};
}
else {
/// If 'f()' is a valid call, just call it, we are done.
return f();
}
}
int
main()
{
auto f = [](auto a, auto b, auto c, auto d) {
return a * b * c * d;
};
return curry(f)(1)(2)(3)(4);
}
See code in action on here. With a similar approach, here is how to curry functions with arbitrary number of arguments.
The same idea seems to work out also in C++14, if we exchange the constexpr if
with a template selection depending on the test needs_unapply<decltype(f)>::value
:
template <typename F> auto
curry(F&& f);
template <bool> struct
curry_on;
template <> struct
curry_on<false> {
template <typename F> static auto
apply(F&& f) {
return f();
}
};
template <> struct
curry_on<true> {
template <typename F> static auto
apply(F&& f) {
return [=](auto&& x) {
return curry(
[=](auto&&...xs) -> decltype(f(x,xs...)) {
return f(x,xs...);
}
);
};
}
};
template <typename F> auto
curry(F&& f) {
return curry_on<needs_unapply<decltype(f)>::value>::template apply(f);
}
Solution 3
Simplifying Gregg's example, using tr1:
#include <functional>
using namespace std;
using namespace std::tr1;
using namespace std::tr1::placeholders;
int f(int, int);
..
int main(){
function<int(int)> g = bind(f, _1, 5); // g(x) == f(x, 5)
function<int(int)> h = bind(f, 2, _1); // h(x) == f(2, x)
function<int(int,int)> j = bind(g, _2); // j(x,y) == g(y)
}
Tr1 functional components allow you to write rich functional-style code in C++. As well, C++0x will allow for in-line lambda functions to do this as well:
int f(int, int);
..
int main(){
auto g = [](int x){ return f(x,5); }; // g(x) == f(x, 5)
auto h = [](int x){ return f(2,x); }; // h(x) == f(2, x)
auto j = [](int x, int y){ return g(y); }; // j(x,y) == g(y)
}
And while C++ doesn't provide the rich side-effect analysis that some functional-oriented programming languages perform, const analysis and C++0x lambda syntax can help:
struct foo{
int x;
int operator()(int y) const {
x = 42; // error! const function can't modify members
}
};
..
int main(){
int x;
auto f = [](int y){ x = 42; }; // error! lambdas don't capture by default.
}
Hope that helps.
Solution 4
Have a look at Boost.Bind which makes the process shown by Greg more versatile:
transform(a.begin(), a.end(), back_inserter(b), bind(f, _1, 5));
This binds 5
to f
's second argument.
It’s worth noting that this is not currying (instead, it’s partial application). However, using currying in a general way is hard in C++ (in fact, it only recently became possible at all) and partial application is often used instead.
Solution 5
If you're using C++14 it's very easy:
template<typename Function, typename... Arguments>
auto curry(Function function, Arguments... args) {
return [=](auto... rest) {
return function(args..., rest...);
}; // don't forget semicolumn
}
You can then use it like this:
auto add = [](auto x, auto y) { return x + y; }
// curry 4 into add
auto add4 = curry(add, 4);
add4(6); // 10
Comments
-
yesraaj almost 4 years
What is currying?
How can currying be done in C++?
Please Explain binders in STL container?
-
ugasoft over 15 years> C++ STL binders provide an implementation of this in C++. yes, but only for unary and binary functions...
-
oz10 over 15 yearsKonrad, since you are using the single-source form of std::transform, shouldn't you be using _1 instead of _2? The fact that you wrote bind(f, 5, _1) instead of bind(f, _1, 5) says that the variable gets plugged into f as the second argument.
-
Greg Hewgill over 15 yearsMarcin: raj requested the C++ example before I added it. :)
-
Erkki Nokso-Koivisto over 15 yearsI wish I could vote up a comment trail. This comment chain is amusing. :)
-
fbrereto over 14 yearsI cannot recommend Boost.Bind enough -- learn it, use it, love it!!
-
Frerich Raabe over 12 yearsActually, I think this answer is wrong; what this answer describes is "partial application", which the
bind
functions do. "Currying" is the process of transforming a function taking N arguments into a function taking one argument and returning a function with N-1 arguments, e.g.void (*)(int, short, bool)
becomesX (*)(int)
withX
beingvoid (*)(short, bool)
. See haskell.org/haskellwiki/Currying for all you ever wanted to know about currying and partial function application. -
Marcin about 12 years@FrerichRaabe You are strictly correct; but the point of currying is to achieve (easy) partial application.
-
Jan Hudec over 11 years@Marcin: I've come to find this question because I want currying and not just any partial application. The difference is that when you have function with 6 arguments carefully written so that you need to fix the first argument, you don't want to put all the placeholders in there!
-
Yakk - Adam Nevraumont over 9 yearsTechnically this is partial function evaluation: a full curry would take a 3 argument function
f
, and allowcurry(f)(3)(2)(1)
before invoking. +1, because partial function evaluation is still useful (and often what people mean by 'curry'), and because of how tight it is. You can improve performance with much more code and perfect forwarding. -
Samer over 9 yearsyou need to explain in wording the answer not just post a code, the OP was not just asking for a code, he was asking for explanation!
-
Oguk over 9 years+1 This is the first answer that actually provides a solution to "How is currying done in C++?". As pointed out pointed out in the comments of some other answers, general currying (as implemented here) is different from partial application of a finite number of specific arguments.
-
Julian over 9 yearscheck also Luc Danton's answer in Partial application with a C++ lambda? which provides also a nice and maybe somewhat more complete implementation on the subject of partial application.
-
Yongwei Wu over 9 yearsThis is the answer I am looking for: implementing currying with variadic function templates.
-
Thomas Eding about 9 yearsYeah... this is NOT currying.
-
Thomas Eding about 9 yearsThis is not currying. This is partial application.
-
Thomas Eding about 9 yearsDon't use double underscores anywhere in your C++ code (unless you are a compiler vendor). It's simply not legal.
-
Konrad Rudolph about 9 years@Thomas You’re absolutely right of course. In fact, I’m super annoyed that the R community uses the wrong terminology fort his. My answer wasn’t actually trying to sell this as currying, but merely showing a better way of implementing the accepted answer. that said, I’ve updated my answer to make this clear.
-
Admin about 9 years@ThomasEding Isn't it legal as long as you don't start with double underscores?
-
Julian about 9 years@ThomasEding: Thx for the comment! I actually didn't know that, since it compiled just fine...
-
Thomas Eding about 9 years@Poldie: You cannot start an identifier with an underscore followed by a capital letter.
-
Admin about 9 years@ThomasEding Or a numeric digit.
-
Ludovic Zenohate Lagouardette over 8 years@ugasoft B-but currying an unary operation is like diluting wine in fermented grappe juice confused
-
Morten over 7 years
std::void_t
is also C++17 but can be replaced: en.cppreference.com/w/cpp/types/void_t -
Admin about 7 yearsWithout any explanation, this is not helpful at all.
-
Kaz over 5 yearsDifference between currying and partial application: partial application takes a function like f(x, y) and binds some of the arguments to specific values, returning a function of fewer arguments. E.g. we might bind y to the specific value of 2, and then return a function h(x) = f(x, 2): h is f, partially applied. h(x) does not denote a function; it denotes the value f(x, 2). Currying does not bind specific values. If we curry f(x, y) by removing the y parameter, we end up with a h(x) which returns a function. h(x) denotes a function g, such that g(y) denotes f(x, y).
-
Kaz over 5 yearsThus currying gives us a "partial application factory". We can choose some value like 2 and then write h(2). This will give us a function g(y) which calls f(2, y): the parameter x has been partially applied. We curried f to obtain h, and then called h with a particular value to induce the partial application of f.
-
underscore_d over 4 years...or with only a little bit more code, and moving the arguments from the outer 'factory' function into the returned lambda! ...or, if they are known always to be unmodified, just take const references, and no need to copy or move anything. That said, until C++20, it's a bit painful to move a variadic pack of arguments to the lambda: before that, you have to stash them in a
tuple
and laterapply
it. -
TamaMcGlinn over 3 years@underscore_d C++20 is here; can this answer be improved now?