Functional composition in c++11

The new functional components in c++11 such as lambda closures takes a welcomed step in the direction of making c++ more functional – in the functional paradigm sense of the word, it still remains a dysfunctional language in the sense that there is still an abundance of rope available for hangers. This post will detail my attempt at using some of that rope to make functional composition available to people who are rightfully reluctant to come close to the capricious coil.

Functional composition is when you call a function with the output of another function. Composing function $f$ with function $g$ yields a third function: $h=f\circ g$, with the definition $h\left(·\right)=g\left(f\left(·\right)\right)$. This mechanism can be generalized to any number of functions (because the composition of two functions is also a function).

This is a good example of inductive definitions, which can be solved using variadic templates treated as a list of templates parameters. The list of parameters are treated as a list in a declarative language like prolog or lisp, and is evaluated at compile time. The basic principle is that a list consists of a first element and a shorter list containing all but the first element. As long as the program knows how to handle a single element, the behavior can be recursively defined as the behavior of each element until some base case is reached. The base case is typically the list containing a single element, or the empty list. For functional composition, the base case will be a single function since the composition of no functions is illdefined. The base case is trivially a call to that one function.

The code will be structured so that there is a recursively defined structure called composition which represents the resulting function, and a convenience function called compose, which takes an arbitrary number of functions as input, and returns a composition.

The compose function is trivial as long as you are familiar with variadic templates and perfect forwarding:

#include <tuple>
#include <functional>
#include <type_traits>

template<typename... funcs_T>
inline composition<funcs_T...> compose(funcs_T&&... funcs) {
  return composition<funcs_T...>(std::forward<funcs_T>(funcs)...);
}

The function merely deduces the type of the composition from the parameters passed in.

The composition structure is where all the interesting stuff happens. First off, we need to declare the existence of the structure, and allow it to be parameterized with any number of functions:

template<typename...> class composition;

Once the structure is declared, we can define the base case and the inductive case. Let’s start with the easier base case, which merely wraps a single function:

template<typename func_T>
class composition<func_T> {
public:
  typedef typename std::decay<func_T>::type func_type;
  inline composition(func_T&& func) : func_m(std::forward<func_T>(func)) {}
  inline composition(const composition&) = default;
  inline composition(composition&&) = default;
  inline composition& operator=(composition x) {
    swap(*this, x);
    return *this;
  }
  friend inline void swap(composition& a, composition& b) {
    using namespace std;
    swap(a.func_m, b.func_m);
  }
  template<typename... args_T>
  inline typename std::result_of<func_type(args_T...)>::type
  operator()(args_T&&... args) const {
    return func_m(std::forward<args_T>(args)...);
  }
protected:
  func_type func_m;
};

To be a good citizen, the class defines copy and move constructors, assignment operator and swap. Other than that, it merely wraps a function, taking care to keep valid storage of it (using std::decay). As the base case, the class has only one template parameter. By specializing the class when there are more than one parameter, we can define the inductive case. Somewhat counter-intuitive, this requires three named parameters: the first function, the “head of the list”, and the “tail of the list”. This is necessary, as the tail is actually a variadic template, and thus allowed to be empty; if there was no explicit head of the list, the definition would conflict with te base case. Compilers can typically handle the conflict, but there is no need to confuse the poor compilers more than necessary. To complete the induction, we can use inheritance to have compoistion<a, b, c> inherit from composition<b, c>. Fulfilling only good citizenry, the class looks like this:

template<typename func_T, typename head_T, typename... tail_T>
class composition<func_T, head_T, tail_T...>
: public composition<head_T, tail_T...>
{
  typedef composition<head_T, tail_T...> base_type;
public:
  typedef typename std::decay<func_T>::type func_type;
  inline composition(func_T&& func, head_T&& head, tail_T&&... tail)
  : base_type(std::forward<head_T>(head), std::forward<tail_T>(tail)...)
  , func_m(std::forward<func_T>(func))
  {}
  inline composition(const composition&) = default;
  inline composition(composition&&) = default;
  inline composition& operator=(composition x) {
    swap(*this, x);
    return *this;
  }
  friend inline void swap(composition& a, composition& b) {
    using namespace std;
    swap(a.func_m, b.func_m);
    swap(static_cast<base_type&>(a), static_cast<base_type&>(b));
  }
protected:
  func_type func_m;
};

Now, all that is missing is the application operator, to actually perform the composed call. Theoretically, it needs to apply the base class to whatever the local function returns. Remember: the first function is applied first, although the nested form puts the first function innermost, which is to the rightmost. The implementation is:

template<typename... args_T>
inline typename std::result_of<base_type(typename std::result_of<func_type(args_T...)>::type)>::type
operator()(args_T&&... args) const {
  return base_type::operator()(func_m(std::forward<args_T>(args)...));
}

The trickiest part of writing it was figuring out the return type.

In the end, this allows us to write programs such as:

int add(int a, int b) { return a + b; }
int add_one(int a) { return a + 1; }

int main(const int argc, const char** argv) {
  using namespace std;
  const auto f = compose(add, add_one);
  int a = f(10, 20);
  assert(a == 31);
  return 0;
}

Note that is would be meaningless to compose the function f with anything, as it requires two parameters, while functions in c++ are limited to returning a single value. Next up, I will show how you can use parameter unpacking to compose functions that return tuples with functions that expect multiple parameters.

comments powered by Disqus