function composition in C++ / C++11

Gabriel L. picture Gabriel L. · Sep 28, 2013 · Viewed 14.3k times · Source

I am currently coding some cryptographic algorithms in C++11 that require a lot of function compositions. There are 2 types of composition I have to deal with :

  1. Compose a function on itself a variable number of times. Mathematically, for a certain function F, F^n(x) = (F^{n-1} o F)(x) = F^{n-1}(F(x)).

  2. Compose different functions together. For example, for some functions f,g,h,i,j and k of the same type, I'll have f(g(h(i(j(k(x)))))).

In my case, I'm using the following definition of F :

const std::vector<uint8_t> F(const std::vector<uint8_t> &x);

I would like to compose this function on itself n times. I have implemented the composition in a simple recursive way which is working fine :

const std::vector<uint8_t> compose(const uint8_t n, const std::vector<uint8_t> &x)
{
    if(n > 1)
       return compose(n-1, F(x));

    return F(x);
}

For this case, is there a more efficient way an proper way to implement this composition using c++11 but without using BOOST ? It would be great to use this form if it is possible of course :

answer = compose<4>(F)(x); // Same as 'answer = F^4(x) = F(F(F(F(x))))'

For the second case, I would like to implement the composition of a variable number of functions. For a given set of functions F0, F1, ..., Fn having the same definition as F, is there an efficient and proper way to compose them where n is variable ? I think variadic template would be useful here, but I don't know how to use them in that case.

Thanks for your help.

Answer

Igor Tandetnik picture Igor Tandetnik · Sep 28, 2013

Something along these lines, perhaps (untested):

template <typename F>
class Composer {
  int n_;
  F f_;
public:
  Composer(int n, F f) : n_(n), f_(f) {}

  template <typename T>
  T operator()(T x) const {
    int n = n_;
    while (n--) {
      x = f_(x);
    }
    return x;
  }
};

template <int N, typename F>
Composer<F> compose(F f) {
  return Composer<F>(N, f);
}

EDIT: And for the second case (tested this time):

#include <iostream>

template <typename F0, typename... F>
class Composer2 {
    F0 f0_;
    Composer2<F...> tail_;
public:
    Composer2(F0 f0, F... f) : f0_(f0), tail_(f...) {}

    template <typename T>
    T operator() (const T& x) const {
        return f0_(tail_(x));
    }
};

template <typename F>
class Composer2<F> {
    F f_;
public:
    Composer2(F f) : f_(f) {}

    template <typename T>
    T operator() (const T& x) const {
        return f_(x);
    }
};

template <typename... F>
Composer2<F...> compose2(F... f) {
    return Composer2<F...>(f...);
}

int f(int x) { return x + 1; }
int g(int x) { return x * 2; }
int h(int x) { return x - 1; }

int main() {
  std::cout << compose2(f, g, h)(42);
  return 0;
}