Function Composition in C++/C++11

function composition in C++ / C++11

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;
}

How to define the function composition in c++17?

BTW, is this really your code? You're not expanding params so it should not compile.

I. The way you define composition, it is indistinguishable from a simple invocation: your fComposition(f, g, arg) is the same as f(g(arg)) except for extra characters typing. The real composition is usually a combinator that accepts two functions and returns a closure that, when invoked on actual arguments, applies them in succession. Something like:

template<class F, class G> auto comp(F f, G g) {
    return [f, g](auto &&... args) {
        return f(g(std::forward<decltype(args)>(args)...));
    };
}

(Note by-values bindings. In C++17, they are more advanced than twenty years ago. :) You can add std::moves and std::forwards by taste.)

This way you compose two functions:

auto fg = comp(f, g);

and later invoke the result on arguments:

auto x = fg(arg1, arg2);

II. But really, why limit ourselves with two operands? In Haskell, (.) is a single binary function. In C++, we can have a whole tree of overloads:

template<class Root, class... Branches> auto comp(Root &&root, Branches &&... branches) {
     return [root, branches...](auto &&...args) {
         return root(branches(std::forward<decltype(args)>(args)...)...);
     };
}

Now you can encapsulate any AST in a single callable:

int f(int x, int y) { return x + y; }
int g(int x) { return x * 19; }
int h(int x) { return x + 2; }

#include <iostream>
int main() {
    auto fgh = comp(f, g, h);
    std::cout << fgh(2) << '\n';
}

A similar technique was the only way known to me to have anonymous closures in C++ prior to 11 standard.

III. But wait, is there a library solution? In fact, yes. From std::bind's description

If the stored argument arg is of type T for which std::is_bind_expression<T>::value == true (for example, another bind expression was passed directly into the initial call to bind), then bind performs function composition: instead of passing the function object that the bind subexpression would return, the subexpression is invoked eagerly, and its return value is passed to the outer invokable object. If the bind subexpression has any placeholder arguments, they are shared with the outer bind (picked out of u1, u2, ...). Specifically, the argument vn in the std::invoke call above is arg(std::forward<Uj>(uj)...) and the type Vn in the same call is std::result_of_t<T cv &(Uj&&...)>&& (cv qualification is the same as that of g).

Sorry, no examples here at this moment. >_<

P.S. And yes, std::round is an overloaded function so you should typecast it to specify which exactly overload you need to be composed.

Function Composition Operator

Unfortunately, C++ does not allow operators to be overloaded for built-in types. Just as you cannot implement your own operator* for two ints, you cannot implement it for two function pointers, except if you represent these functions with the std::function type which is a class and therefore not a built-in type.

You can, however, instead of using an operator, simply use a function:

std::function<float(float)> dot(float(*func1)(float) , float(*func2)(float))
{
   return [func1, func2](float x) { return func1(func2(x)); };
}

Function Composition in C++

I don't know of anything that supports the syntax you wish for currently. However, it would be a simple matter to create one. Simply override * for functors (boost::function<> for example) so that it returns a composite functor.

template < typename R1, typename R2, typename T1, typename T2 >
boost::function<R1(T2)> operator * (boost::function<R1(T2)> const& f, boost::function<R2(T2)> const& g)
{
  return boost::bind(f, boost::bind(g, _1));
}

Untested, but I suspect it's close if it doesn't work out of the box.

Functional composition with variadic templates in C++11

If I got it correctly, you need no fancy template magic to do this composition. Here is the almost self-explanatory code:

#include <functional>
#include <string>
#include <iostream>

// it is just an std::function taking A and returning B
template <typename A, typename B>
using Arrow = std::function<B(const A&)>;

// composition operator: just create a new composed arrow
template <typename A, typename B, typename C>
Arrow<A, C> operator*(const Arrow<A, B>& arr1, const Arrow<B, C>& arr2)
{
    // arr1 and arr2 are copied into the lambda, so we won't lose track of them
    return [arr1, arr2](const A& a) { return arr2(arr1(a)); };
}

int main()
{
    Arrow<int, float> plusHalf([](int i){return i + 0.5;});
    Arrow<float, std::string> toString([](float f){return std::to_string(f);});

    auto composed = plusHalf * toString; // composed is Arrow<int, std::string>
    std::cout << composed(6) << std::endl; // 6.5

    //auto badComposed = toString * plusHalf; // compile time error
}

I mostly played with lambda functions here.

Using a single function call instead of a operator chain proved to be a more tricky problem. This time you got some templates:

#include <functional>
#include <string>
#include <iostream>

// it is just an std::function taking A and returning B
template <typename A, typename B>
using Arrow = std::function<B(const A&)>;

// A helper struct as template function can't get partial specialization
template <typename... Funcs>
struct ComposerHelper;

// Base case: a single arrow
template <typename A, typename B>
struct ComposerHelper<Arrow<A, B>>
{
    static Arrow<A, B> compose(const Arrow<A, B>& arr)
    {
        return arr;
    }
};

// Tail case: more arrows
template <typename A, typename B, typename... Tail>
struct ComposerHelper<Arrow<A, B>, Tail...>
{
    // hard to know the exact return type here. Let the compiler figure out
    static auto compose(const Arrow<A, B>& arr, const Tail&... tail)
    -> decltype(arr * ComposerHelper<Tail...>::compose(tail...))
    {
        return arr * ComposerHelper<Tail...>::compose(tail...);
    }
};

// A simple function to call our helper struct
// again, hard to write the return type
template <typename... Funcs>
auto compose(const Funcs&... funcs)
-> decltype(ComposerHelper<Funcs...>::compose(funcs...))
{
    return ComposerHelper<Funcs...>::compose(funcs...);
}

using namespace std;

int main()
{
    Arrow<int, float> plusHalf([](int i){return i + 0.5;});
    Arrow<float, string> toString([](float f){return to_string(f);});
    Arrow<string, int> firstDigit([](const string& s){return s[0]-'0';});

    auto composed = compose(plusHalf, toString, firstDigit);
    // composed is Arrow<int, int>

    std::cout << composed(61) << std::endl; // "6"

    //auto badComposed = compose(toString, plusHalf); // compile time error
}

Nested function pointers or function composition

If you want some sort of run-time control over the composition, you could write a function that evaluates an array of function pointers as a composition:

// calls functions in reverse order
double compose(size_t n, double (* const fc[])(double), double x)
{
    while (n--)
    {
        x = fc[n](x);
    }
    return x;
}

This could be called from another version of your derivative function:

double derivative_composed(size_t n, double (* const fc[])(double), double x)
{
    // Example implementation for illustrative purpose only.
    double fx, fxh, h;
    h = x / 1e10;
    if (h == 0)
    {
        h = 1e-10;
    }
    fx = compose(n, fc, x);
    fxh = compose(n, fc, x + h);
    return (fxh - fx) / h;
}

To avoid repeated code, your original derivative function could be changed to be a wrapper that calls derivative_composed with a single function:

double derivative(double (* const f), double x)
{
    return derivative_composed(1, &f, x);
}

Example usage:

int main(void)
{
    double (* const fc[2])(double) = { exp, cos };
    double x = 1.0;
    double xprime = derivative_composed(2, fc, x);
    printf("x = %f, xprime = %f\n", x, xprime);
}

Output:

x = 1.000000, xprime = -1.444407

Is it possible in C++11 to combine functions into a new function?

You can write something along the lines of:

#include <functional>
#include <iostream>

template<class F>
F compose(F f, F g)
{
  return [=](int x) { return f(g(x)); };
}

int main()
{
  std::function<int (int)> f = [](int i) { return i * 2; };
  std::function<int (int)> g = [](int i) { return i + 10; };

  auto c = compose(f, g);
  std::cout << c(20) << '\n';  // prints 60
}

The code can be simply extended to cover the second half of the question:

template<class F>
F compose(F f, unsigned n)
{
  auto g = f;

  for (unsigned i = 0; i < n; ++i)
    g = compose(g, f);

  return g;
}

int main()
{
  std::function<int (int)> h = [](int i) { return i * i; };

  auto d = compose(h, 1);
  auto e = compose(h, 2);
  std::cout << d(3) << "\n"    // prints 81
            << e(3) << "\n";   // prints 6561
}

NOTE. Here using std::function. It isn't a lambda but wraps a lambda with a performance cost.

---

Related Topics