C++11 treats functions as first-class citizens and this gives us ability to construct a lot of nice things as design patterns borrowed from functional languages. Meanwhile C++ has very powerful template metaprogramming. This post is aimed to make templated functions closer to first-class citizens, and to construct some simplicity and beauty which you can get from it.
Also here will be implementation for currying of such functions! If you don’t know what currying is – just remember std::bind.
And to make it shine we’ll add piping. (This article will improve some ideas from post about functional piping ). This step is optional and you can replace such piping with commas and function calls.
TEMPLATE TO SIMPLE FUNCTOR
Ok, let’s start from very simple template function.
1 2 3 4 5 |
template <typename T> void print(T t) { cout << t << endl; } |
I will use different styles of code colouring here to indicate difference between example code and inner implementation which is similar for all cases.
To pass it to some function we need to wrap it into functor:
1 2 3 4 5 6 7 8 |
class tfn_print { public: template <typename... Args> auto operator()(Args&&... args) const ->decltype(print(std::forward<Args>(args)...)) { return print(std::forward<Args>(args)...); } } |
Here operator() is overloaded to pass all arguments to print template. As we will modify this functor to cover all cases, the list of arguments is provided using variadic templates. Note: you can define all functions inside such wrappers from the start, but there is way to do it through macro:
1 2 3 |
#define make_citizen(X) class tfn_##X { public: template <typename... Args> auto operator()(Args&&... args) const ->decltype(X(std::forward<Args>(args)...)) { return X(std::forward<Args>(args)...); } } make_citizen(print); |
This small macro creates class from templated function.
Important note for macro haters. Yes, macros should be avoided when you can substitute them using variadic templates and other new stuff. But still there are some cases when you can’t do that. So when you have couple of very small obvious macro definitions which will make your code considerably smaller, more readable and maintainable – use it. Such cases are rare and when it happens C++ committee should look upon it and add some means into the language itself to fix it.
Example:
1 2 3 4 5 6 |
// testing print... { tfn_print print; print(5); print("hello"); } |
We redefined print in smaller scope as instance of object. Now we can use it as function and pass as argument to another function. Note that the same function is used with arguments of different type – so no need to create distinct functors.
Next we will create some additional instruments to work with such ‘templated’ functors more effectively.
PASS TUPLE TO FUNCTION AS ARGUMENT LIST
As we will use such ability later – let’s write simple function which will expand std::tuple and feed results into the given function.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// apply tuple to function... namespace fn_detail { template<int ...> struct int_sequence {}; template<int N, int ...S> struct gen_int_sequence : gen_int_sequence<N-1, N-1, S...> {}; template<int ...S> struct gen_int_sequence<0, S...> { typedef int_sequence<S...> type; }; template <typename F, typename... Args, int... S> inline auto fn_tuple_apply(int_sequence<S...>, const F& f, const std::tuple<Args...>& params) -> decltype( f((std::get<S>(params))...) ) { return f((std::get<S>(params))...); } } template <typename F, typename... Args> inline auto fn_tuple_apply(const F& f, const std::tuple<Args...>& params) -> decltype( f(std::declval<Args>()...) ) { return fn_detail::fn_tuple_apply(typename fn_detail::gen_int_sequence<sizeof...(Args)>::type(), f, params); } |
In C++14 this could be done a bit shorter using std::integer_sequence, but at the moment I’m forced to use just C++11 ( to compile things for Android for example). The sequence of integer indices S is constructed through template recursion, and than is passed as additional argument for unpacking. This is just one of possible implementations.
Usage:
1 2 3 4 5 6 |
auto f = [](int x, int y, int z) { return x + y - z; }; auto params = make_tuple(1,2,3); auto res = fn_tuple_apply(f, params); print(res); // Result: 0 |
The next step is the idea that you can combine function input parameters into tuple using several steps instead of one std::make_tuple call.
TUPLE CONCATENATION
For concatenation of tuples C++11 has function named std::tuple_cat. To make things more compact we can overload << operator to add new parameter into tuple.
1 2 3 4 5 6 |
// tuple concatenation via << operator template<typename... OldArgs, typename NewArg> tuple<OldArgs...,NewArg> operator<<(const tuple<OldArgs...> & t, const NewArg& arg) { return std::tuple_cat(t, std::make_tuple(arg)); } |
Usage:
1 2 3 4 5 |
auto list = make_tuple(1,4); auto res2 = fn_tuple_apply(f, list << 4); // f(1,4,4) print(res2); // Result: 1 |
FUNCTIONAL PIPELINE
See post about functional piping to get the idea (we use different implementation for piping here). Anyway, this step is optional and you can replace such piping with commas and function calls, but piping here looks very nice.
First simple overload will provide ability to pipe single argument into function:
1 2 3 4 5 6 |
// pipe single argument into function via | operator template<typename T, class F> auto operator|(T&& param, const F& f) -> decltype(f(param)) { return f(std::forward<T>(param)); } |
Usage:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Return count of elements as templated operator template <typename T> int count(const T& container) { return container.size(); } make_citizen(count); { tfn_count count; vector<string> slist = {"one", "two", "three"}; slist | count | print; } // Result: 3 |
One new sample template function count() is just returning size() of provided collection. We provide the list of three strings into count function and after that pipe the result into print().
This is nice but application seems to be rather limited as functions tend to have more than one argument. Let’s solve this using some curry…
CURRYING
Currying in C++11 is usually made using std::bind, which is flexible and useful for a lot of cases. But we can’t use it for templates. So let’s create some wrapper class which will implement curry and provide the simplest way to work with it inside pipelines.
General way (like in haskell) is to curry from left to right argument – so call f(1,2,3) is equivalent to f(1)(2)(3). But in piping example everything is slightly different –f(1,2,3) is equivalent to 1 | f(2,3). In other words I want to curry both ways – left and right. Yes, std::bind gives ability to specify any order but this is for price of a bit longer syntax that it’s required in general cases. And haskell’s syntax is not so good also, imho. That’s because it’s hard for programmer to identify difference between currying and function call. So here i’m using different syntax (and this decision is optional) where you have separate operators for function call and argument curry.
The next class is called fn_universal as representation of some function which is polymorphic (in sense that it can accept arguments of different types) and can be used with currying and piping. May be this class will be extended further later. You might want to rename it to fn_curryed or something like it.
Of course, to hold arguments we will use tuples. The implementation:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
// universal function / extended function wrapper ! template<typename F, typename TPackBefore = std::tuple<>, typename TPackAfter = std::tuple<>> class fn_universal { private: F f; ///< main functor TPackAfter after; ///< curryed arguments TPackBefore before; ///< curryed arguments public: fn_universal(F && f) : f(std::forward<F>(f)), after(std::tuple<>()), before(std::tuple<>()) {} fn_universal(const F & f, const TPackBefore & before, const TPackAfter & after) : f(f), after(after), before(before) {} template <typename... Args> auto operator()(Args... args) const -> decltype( fn_tuple_apply(f, std::tuple_cat(before, make_tuple(args...), after)) ) { // execute via tuple return fn_tuple_apply(f, std::tuple_cat(before, make_tuple(std::forward<Args>(args)...), after)); } // curry template <typename T> auto curry(T && param) const -> decltype(fn_universal<F,decltype(std::tuple_cat(before, std::make_tuple(param))),TPackAfter>(f, std::tuple_cat(before, std::make_tuple(param)), after)) { return fn_universal<F,decltype(std::tuple_cat(before, std::make_tuple(param))),TPackAfter>(f, std::tuple_cat(before, std::make_tuple(std::forward<T>(param))), after); } template <typename T> auto curry_right(T && param) const -> decltype(fn_universal<F, TPackBefore, decltype(std::tuple_cat(after, std::make_tuple(param)))>(f, before, std::tuple_cat(after, std::make_tuple(param)))) { return fn_universal<F, TPackBefore, decltype(std::tuple_cat(after, std::make_tuple(param)))>(f, before, std::tuple_cat(after, std::make_tuple(std::forward<T>(param)))); } }; |
Note that class is immutable.
The main nice thing about this class: there is no restriction on types or count of arguments. All what is done here is combining provided arguments into two tuples – right and left parameters. And when time comes to execute function we just combine everything into single tuple and feed this tuple into function. So you can curry function which supports variadic number of arguments!
And to provide easy interface for currying I use the following overloads for operators:
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// left curry by << operator template<typename UF, typename Arg> auto operator<<(const UF & f, Arg && arg) -> decltype(f.template curry<Arg>(std::forward<Arg>(arg))) { return f.template curry<Arg>(std::forward<Arg>(arg)); } // right curry by >> operator template<typename UF, typename Arg> auto operator>>(const UF & f, Arg && arg) -> decltype(f.template curry_right<Arg>(std::forward<Arg>(arg))) { return f.template curry_right<Arg>(std::forward<Arg>(arg)); } |
Let’s add small builder helper. Also (very optional) I might add definition macro to make examples a bit shorter.
1 2 3 4 5 6 7 |
template <typename F> auto fn_to_universal(F && f) -> fn_universal<F> { return fn_universal<F>(std::forward<F>(f)); } #define make_universal(NAME, F) make_citizen(F); const auto NAME = fn_to_universal(tfn_##F()); |
This line is just defining new ‘universal’ function from given template function. You could change this using more convenient way.
EXAMPLES FOR CURRYING
Trivial examples:
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// currying.... auto f = [](int x, int y, int z) { return x + y - z; }; auto uf = fn_to_universal(f); auto uf1 = uf << 1; auto uf2 = uf1 << 2 << 5; uf2() | print; // result: -2 // Piping: 1 | (uf << 4 << 6) | print; // 4+6-1 = 9 3 | (uf >> 6 >> 7) | print; // 3+6-7 = 2 |
Note the order of arguments. Not so complicated to read.
Now let’s write couple of template functions to get some realistic examples. This will look like functional operators. I even could mark these functions as inner implementation as they are so common, but to underline that you have the ability to control this behaviour yourself I leave it marked as sample:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
// MAP template <typename T, typename... TArgs, template <typename...>class C, typename F> auto fn_map(const C<T,TArgs...>& container, const F& f) -> C<decltype(f(std::declval<T>()))> { using resultType = decltype(f(std::declval<T>())); C<resultType> result; for (const auto& item : container) result.push_back(f(item)); return result; } // REDUCE (FOLD) template <typename TResult, typename T, typename... TArgs, template <typename...>class C, typename F> TResult fn_reduce(const C<T,TArgs...>& container, const TResult& startValue, const F& f) { TResult result = startValue; for (const auto& item : container) result = f(result, item); return result; } // FILTER template <typename T, typename... TArgs, template <typename...>class C, typename F> C<T,TArgs...> fn_filter(const C<T,TArgs...>& container, const F& f) { C<T,TArgs...> result; for (const auto& item : container) if (f(item)) result.push_back(item); return result; } make_universal(fmap, fn_map); make_universal(reduce, fn_reduce); make_universal(filter, fn_filter); |
It’s obvious that such primitives can be reused avoiding a lot of code duplication.
And one minor function – make sum of all arguments:
1 2 3 4 5 6 7 8 9 |
template <typename T, typename... Args> T sum_impl(T arg, Args... args) { T result = arg; [&result](...){}((result += args, 0)...); return result; } make_universal(sum, sum_impl); |
Here could be more trivial implementation and couple of overloads, but to show that you have no limitation with count of arguments I leave it like this.
Also we can modify print to handle any amount of arguments:
1 2 3 4 5 6 7 |
template <typename... Args> void print(Args... args) { (void)(int[]){((cout << args), 0)...}; cout << endl; } auto uprint = fn_to_universal(print); |
AND NOW: Let’s try this in action:
1 2 3 4 5 6 7 8 9 10 11 12 13 |
vector<string> slist = {"one", "two", "three"}; // all strings as one slist | (reduce >> string("") >> sum) | (uprint << "All: "); // All: onetwothree // sum of elements of array vector<int>{1,2,3} | (reduce >> 0 >> sum) | (uprint << "Sum: "); // Sum: 6 // count sum length of all strings in the list slist | (fmap >> count) | (reduce >> 0 >> sum) | (uprint << "Total: " >> " chars"); // Total: 11 chars |
This is quite readable and functional-style code. Not the one we could expect from C++.
So the idea is that now we can write small universal templates and combine them in pipelines as we like. Looks great!
Consider small templates as small universal building blocks.
More examples…
Let’s assume we are working with some business data like collection of users.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
template <typename T, typename TName> bool isNameEqualImpl(const T& obj, const TName& name) { return (obj->name == name); } make_universal(isName, isNameEqualImpl); template <typename T, typename TId> bool isIdEqualImpl(const T& obj, const TId& id) { return (obj->id == id); } make_universal(isId, isIdEqualImpl); template <typename T> bool isNotNullImpl(const T& t) { return (t != nullptr); } make_universal(isNotNull, isNotNullImpl); template <typename F, typename TKey, typename T, typename... TArgs, template <typename...>class C> T findOneImpl(const C<T,TArgs...>& container, const F& f, const TKey& key) { for (const auto& item : container) if (f(item, key)) return item; return nullptr; } make_universal(ffind, findOneImpl); |
First 3 methods are trivial – checking that name or id fields are equal to given values and that whole object is not null.
The last one is find method inside container (we assume here that business data items are presented as immutable structures inside smart pointers). Find receives one function as validate functor and key argument to pass to this validator. Let’s see how to use it:
1 2 3 4 5 6 7 8 |
// example data vector<User> users {make<User>(1, "John", 0), make<User>(2, "Bob", 1), make<User>(3, "Max", 1)}; users | (filter >> (isName >> "Bob")) | ucount | uprint; // 1 users | (filter >> (isId >> 13)) | ucount | uprint; // 0 vector<int>{1,2,6} | (fmap >> (ffind << users << isId)) | (filter >> isNotNull) | ucount | uprint; // 2 |
Such examples do not require an explanation I suppose!
We can convert user names to xml like this:
1 2 3 4 5 6 7 8 9 10 11 |
string xmlWrapImpl(string name, string item) { return "<" + name + ">" + item + "</" + name + ">"; } make_universal(xmlWrap, xmlWrapImpl); // Produce XML users | fmap >> [](User u){ return u->name; } | fmap >> (xmlWrap << "name") | reduce >> string("") >> sum | xmlWrap << "users" | print; // result: <users><name>John</name><name>Bob</name><name>Max</name></users> |
As you can see we can still use lambdas inside expressions.
FUNCTIONAL CHAINS
Now let’s add one more important element to proposed scheme. I want to be able to compose pipeline of functions, store it under some name and then call it multiple times as single function. In other words i want this:
1 2 3 |
auto countUsers = chain((fmap >> (ffind << users << isId)) | (filter >> isNotNull) | ucount); vector<int>{1,2,6} | countUsers | (uprint << "count of users: "); |
In fact this is simple functional composition (like the one discussed in appendix here ), and it can be implemented with ease in case of general functions. But when we are talking about templates things become a bit more complicated. But this is still possible!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
// -------------------- chain of functors ---------------------> // The chain of functors ... is actualy just a tuple of functors template <typename... FNs> class fn_chain { private: const std::tuple<FNs...> functions; template <std::size_t I, typename Arg> inline typename std::enable_if<I == sizeof...(FNs) - 1, decltype(std::get<I>(functions)(std::declval<Arg>())) >::type call(Arg arg) const { return std::get<I>(functions)(std::forward<Arg>(arg)); } template <std::size_t N, std::size_t I, typename Arg> struct final_type : final_type<N-1, I+1, decltype(std::get<I>(functions)(std::declval<Arg>())) > {}; template <std::size_t I, typename Arg> struct final_type<0, I, Arg> { using type = decltype(std::get<I>(functions)(std::declval<Arg>())); }; template <std::size_t I, typename Arg> inline typename std::enable_if<I < sizeof...(FNs) - 1, typename final_type<sizeof...(FNs) - 1 - I, I, Arg>::type >::type call(Arg arg) const { return this->call<I+1>(std::get<I>(functions)(std::forward<Arg>(arg))); } public: fn_chain() {} fn_chain(std::tuple<FNs...> functions) : functions(functions) {} // add function into chain template< typename F > inline auto add(const F& f) const -> fn_chain<FNs..., F> { return fn_chain<FNs..., F>(std::tuple_cat(functions, std::make_tuple(f))); } // call whole functional chain template <typename Arg> inline auto operator()(Arg arg) const -> decltype(this->call<0,Arg>(arg)) { return call<0>(std::forward<Arg>(arg)); } }; |
How this works? When constructing such chain we just put functors into tuple. Tricky part comes when we need to call the function – we need to construct universal caller without knowing function specifications. This is possible using compile-time recursion and std::decltype/std::declval. Creating dummy arguments we go through whole chain recursively and detect final result type.
And to make it work under GCC i hit one of compiler bugs – inside call method recursion during type detection you need to add ‘this->‘ to make it compile (bug).
And to chain functors into the list we need to overload | operator again:
1 2 3 4 5 |
template<typename... FNs, typename F> inline auto operator|(fn_chain<FNs...> && chain, F&& f) -> decltype(chain.add(f)) { return chain.add(std::forward<F>(f)); } |
Now we can use this whole concept like:
1 2 3 4 5 6 7 8 9 10 11 12 |
// Use functional chain: auto f1 = [](int x){ return x+3; }; auto f2 = [](int x){ return x*2; }; auto f3 = [](int x) { return (double)x / 2.0; }; auto f4 = [](double x) { return SS::toString(x); }; auto f5 = [](string s) { return "Result: " + s; }; auto testChain = fn_chain<>() | f1 | f2 | f3 | f4 | f5; // execution: testChain(3) | print; auto countUsers = fn_chain<>() | (fmap >> (ffind << users << isId)) | (filter >> isNotNull) | ucount; vector<int>{1,2,6} | countUsers | (uprint << "count of users: "); |
Note that we use different types during chain execution.
So now we have the ability to store and combine pipelines as we like. Nice.
FINAL TOUCH – MONADIC PIPING (OPTIONAL)
This part is optional but it fits so well… because here will be very smooth shift to monads. Smooth and easy.
What if we change the direction of piping? Let’s pipe functions into data instead piping data into functions! Of cause, we can’t do this with raw data – we need some object to wrap it and call received functions for us. This object can do some additional manipulations with functions along the way. And yes, thats a kind of monad.
Why we need this kind of stuff? Because we can gain additional control of functional chain evaluation.
As example i’ll use maybe monad – which has very simple logic: if we have nullptr as output from any function in chain – we don’t execute further and report empty state. This is kind of implicit error protection.
Implementation will be a bit extended to support pointer and non-pointer types.
Also, this is not ‘true’ monad as true monadic bind operation requieres functions which return monad as result. But using the following implementation you can apply normal functions without any modifications.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
// ------------------ maybe --------------------------> enum class maybe_state { normal, empty }; template <typename T> typename std::enable_if< std::is_object<decltype(T()) >::value, T>::type set_empty() { return T(); } template<> int set_empty<int>() { return 0; } template<> string set_empty<string>() { return ""; } template<typename T> class maybe { private: const maybe_state state; const T x; template <typename R> maybe<R> fromValue(R&& result) const { return maybe<R>(std::forward<R>(result)); } template <typename R> maybe<std::shared_ptr<R>> fromValue(std::shared_ptr<R>&& result) const { if (result == nullptr) return maybe<std::shared_ptr<R>>(); else return maybe<std::shared_ptr<R>>(std::forward<std::shared_ptr<R>>(result)); } public: // monadic return maybe(T&& x) : x(std::forward<T>(x)), state(maybe_state::normal) {} maybe() : x(set_empty<T>()), state(maybe_state::empty) {} // monadic bind template <typename F> auto operator()(F f) const -> maybe<decltype(f(std::declval<T>()))> { using ResultType = decltype(f(std::declval<T>())); if (state == maybe_state::empty) return maybe<ResultType>(); return fromValue(f(x)); } // extract value T getOr(T&& anotherValue) const { return (state == maybe_state::empty) ? anotherValue : x; }; }; template<typename T, typename F> inline auto operator|(maybe<T> && monad, F&& f) -> decltype(monad(f)) { return monad(std::forward<F>(f)); } template<typename T, typename TDefault> inline T operator||(maybe<T> && monad, TDefault&& t) { return monad.getOr(std::forward<TDefault>(t)); } template <typename T> maybe<T> just(T&& t) { return maybe<T>(std::forward<T>(t)); } |
This class can be extended to handle error messages and so on.
I use the same pipe | operator here because its ‘unix’ meaning is perfectly applicable here.
Examples:
1 2 3 4 5 6 7 8 9 10 11 |
maybe<int>(2) | (ffind << users << isId) | [](User u){ return u->name; } | [](string s){ cout << s << endl; return s; }; // Bob (maybe<int>(6) | (ffind << users << isId) | [](User u){ return u->name; }).getOr("Not found") | (uprint << "User: "); // User: Not found just(vector<int>{1,2,6}) | countUsers | [&](int count){ count | (uprint << "Count: "); return count; }; // Count: 2 |
So here we execute processing chain on non existing user and nothing bad happens. Also we can pipe our saved chain countUsers into maybe as expected.
I could produce a lot of other examples here, but may be this is nice topic for another post.
CONCLUSION
Using compile-time recursion and type-detection you can create powerful tools for combining templated functional blocks. Using currying and piping together with functional chains gives very flexible instrument to build compact functional-style methods in C++11. Monadic execution could be added to this scheme without any problems.
Full working sample on github: gist
ps. About templating – i think usage of templates in production should be very minimalistic because template overuse can lead to very unmaintainable code. So when using proposed scheme keep in mind that all blocks should be very small and logically reasonable.