Operator composition in c++

function composition
composition operator
aggregation and composition in c++
composition c++ example
composition operator haskell
composition c++ geeksforgeeks
function composition in python example
functional composition

I'm wondering if there is an elegant solution for composing mathematical operators in C++. By operator, I mean something like the following:

template<class H>
class ApplyOp {
    H h;
public:
    ApplyOp(){}
    ApplyOp(H h_i) : h(h_i) {}

    template<class argtype>
    double operator()(argtype f,double x){
        return h(x)*f(x);
    }
};

The above class makes use of a "helper function" h(x). For example,

struct Helper{
    Helper(){}
    double operator()(double x){return x*x;}
};

struct F{
    F(){}
    double operator()(double x){return exp(x);}
};

int main()
{
    Helper h;
    F f;
    ApplyOp<Helper> A(h);

    std::cout<<"A(f,2.0) = "<<A(f,2.0)<<std::endl; //Returns 2^2*exp(2) = 29.5562...

    return 0;
}

Now, I would like to compose the operator twice or more times, i.e. compute A^2(f,2.0). In the above example, this would return h(x)*h(x)*f(x). Note that this is not function composition, i.e. I do not want to compute A(A(f,2.0),2.0). Rather, think in terms of computing powers of a matrix: if h(x) = M (a matrix), I want M*M*...*M*x.

I was able to use std::bind() to achieve my desired result for A^2 (but not higher powers!) as follows:

auto g = std::bind(&ApplyOp<Helper>::operator()<F>,&A,f,std::placeholders::_1);

With the resulting g, I can apply A^2(f,2.0) by simply calling A(g,2.0). With the above examples, this would return h(x)*h(x)*f(x) = x*x*x*x*exp(x)

How would I generalize this to iteratively applying the operator A N times? I really liked the answer posted here, but it doesn't quite work here. I tried doing nested std:binds but quickly got into deep compiler errors.

Any ideas?

Complete working example:

#include<iostream>
#include<math.h>
#include<functional> //For std::bind

template<class H>
class ApplyOp {
    H h;
public:
    ApplyOp(){}
    ApplyOp(H h_i) : h(h_i) {}

    template<class argtype>
    double operator()(argtype f,double x){
        return h(x)*f(x);
    }
};

struct Helper{
    Helper(){}
    double operator()(double x){return x*x;}
};

struct F{
    F(){}
    double operator()(double x){return exp(x);}
};

int main()
{
    Helper h;
    F f;
    ApplyOp<Helper> A(h);

    std::cout<<"A(f,2.0) = "<<A(f,2.0)<<std::endl; //Returns 2^2*exp(2) = 29.5562...

    auto g = std::bind(&ApplyOp<Helper>::operator()<F>,&A,f,std::placeholders::_1);

    std::cout<<"A^2(f,2.0) = "<<A(g,2.0) <<std::endl; //Returns 2^4*exp(2) = 118.225... 

    return 0;
}

Try this, using template specialization

#include<iostream>
#include<math.h>
#include<functional> //For std::bind

template<class H>
class ApplyOp {
    H h;
public:
    ApplyOp(){}
    ApplyOp(H h_i) : h(h_i) {}

    template<class argtype>
    double operator()(argtype f,double x){
        return h(x)*f(x);
    }
};

struct Helper{
    Helper(){}
    double operator()(double x){return x*x;}
};

struct F{
    F(){}
    double operator()(double x){return exp(x);}
};

// C++ doesn't permit recursive "partial specialization" in function
// So, make it a struct instead
template<typename T, typename U, typename W, int i>
struct Binder {
    auto binder(U b, W c) {
        // Recursively call it with subtracting i by one
        return [&](T x){ return b(Binder<T, U, W, i-1>().binder(b, c), x); };
    }
};

// Specialize this "struct", when i = 2
template<typename T, typename U, typename W>
struct Binder<T, U, W, 2> {
    auto binder(U b, W c) {
        return [&](T x){ return b(c, x); };
    }
};

// Helper function to call this struct (this is our goal, function template not
// struct)
template<int i, typename T, typename U, typename W>
auto binder(U b, W d) {
    return Binder<T, U, W, i>().binder(b, d);
}

int main()
{
    Helper h;
    F f;
    ApplyOp<Helper> A(h);

    std::cout<<"A(f,2.0) = "<<A(f,2.0)<<std::endl; //Returns 2^2*exp(2) = 29.5562...

    // We don't need to give all the template parameters, C++ will infer the rest
    auto g = binder<2, double>(A, f);

    std::cout<<"A^2(f,2.0) = "<<A(g,2.0) <<std::endl; //Returns 2^4*exp(2) = 118.225... 

    auto g1 = binder<3, double>(A, f);

    std::cout<<"A^3(f,2.0) = "<<A(g1,2.0) <<std::endl; //Returns 2^6*exp(2) = 472.2

    auto g2 = binder<4, double>(A, f);

    std::cout<<"A^4(f,2.0) = "<<A(g2,2.0) <<std::endl; //Returns 2^8*exp(2) = 1891.598... 

    return 0;
}

I'm wondering if there is an elegant solution for composing mathematical operators in C++. By operator, I mean something like the following: built-in and (in C++) overloadable functions This is a list of operators in the C and C++ programming languages. All the operators listed exist in C++; the fourth column "Included in C", states whether an operator is also present in C. Note that C does not support operator overloading.

From what I could understand from you question, you are essentially trying to define

A^1(h, f, x) = h(x) * f(x)
A^n(h, f, x) = h(x) * A^(n-1)(h, f, x)

If you are open to using C++17, here is something you can build upon:

#include <iostream>
#include <math.h>

template <int N>
struct apply_n_helper {
  template <typename H, typename F>
  auto operator()(H h, F f, double x) const {
    if constexpr(N == 0) {
      return f(x);
    } else {
      return h(x) * apply_n_helper<N - 1>()(h, f, x);
    }
  }
};

template <int N>
constexpr auto apply_n = apply_n_helper<N>();

int main() {
  auto sqr = [](double x) { return x * x; };
  auto exp_ = [](double x) { return exp(x); };

  std::cout << apply_n<100>(sqr, exp_, 2.0) << '\n';
  std::cout << apply_n<200>(sqr, exp_, 2.0) << '\n';
  return 0;
}

If C++17 is not an option, you can easily rewrite this to use template specializations instead of constexpr-if. I will leave this as an exercise. Here is a link to compiler explorer with this code: https://godbolt.org/z/5ZMw-W

EDIT Looking back at this question, I see that you are essentially trying to compute (h(x))^n * f(x) in a manner so that you don't have to actually do any looping at runtime and the generated code is equivalent to something like:

auto y = h(x);
auto result = y * y * ... * y * f(x)
              \_____________/
                  n times
return result;

Another way of achieving this would be to have something as follows

#include <cmath>
#include <iostream>

template <size_t N, typename T>
T pow(const T& x) {
    if constexpr(N == 0) {
        return 1;
    } else if (N == 1) {
        return x;
    } else {
        return pow<N/2>(x) * pow<N - N/2>(x);
    }
}

template <int N>
struct apply_n_helper {
    template <typename H, typename F>
    auto operator()(H h, F f, double x) const {
        auto tmp = pow<N>(h(x));
        return tmp * f(x);
    }
};

template <int N>
constexpr auto apply_n = apply_n_helper<N>();

int main()
{
    auto sqr = [](double x) { return x * x; };
    auto exp_ = [](double x) { return exp(x); };

    std::cout << apply_n<100>(sqr, exp_, 2.0) << '\n';
    std::cout << apply_n<200>(sqr, exp_, 2.0) << '\n';
    return 0;
}

Here, the usage of pow function is saving us from evaluating h(x) several times.

Compositions are one of the easiest relationship types to implement in C++. They are friend std::ostream& operator<<(std::ostream& out, const Point2D &point). Composition relationships are part-whole relationships where the part must constitute part of the whole object. For example, a heart is a part of a person’s body. The part in a composition can only be part of one object at a time. A heart that is part of one person’s body can not be part of someone else’s body at the same time.

I mean you can use a other class:

template <typename T, std::size_t N>
struct Pow
{
    Pow(T t) : t(t) {}

    double operator()(double x) const
    {
        double res = 1.;

        for (int i = 0; i != N; ++i) {
            res *= t(x);
        }
        return res;
    }

    T t;  
};

And use

ApplyOp<Pow<Helper, 2>> B(h); instead of ApplyOp<Helper> A(h);

Demo

Function composition. Create a function, compose, whose two arguments f and g, are both functions with one argument. The result of compose is to be a function of one argument, (lets call the argument x), which works like applying function f to the result of applying function g to x. The operator “=” is an assignment operator in C++ and it assigns a value to the objects on the left. C++ provides capability to combine assignment operator with almost all the operation we have discussed above and forms a “Composite Assignment Operator”.

So you want to be able to multiply functions. Well, that sounds good. Why not + and - and / while we are in there?

template<class F>
struct alg_fun;

template<class F>
alg_fun<F> make_alg_fun( F f );

template<class F>
struct alg_fun:F {
  alg_fun(F f):F(std::move(f)){}
  alg_fun(alg_fun const&)=default;
  alg_fun(alg_fun &&)=default;
  alg_fun& operator=(alg_fun const&)=default;
  alg_fun& operator=(alg_fun &&)=default;

  template<class G, class Op>
  friend auto bin_op( alg_fun<F> f, alg_fun<G> g, Op op ) {
    return make_alg_fun(
      [f=std::move(f), g=std::move(g), op=std::move(op)](auto&&...args){
        return op( f(decltype(args)(args)...), g(decltype(args)(args)...) );
      }
    );
  }

  template<class G>
  friend auto operator+( alg_fun<F> f, alg_fun<G> g ) {
    return bin_op( std::move(f), std::move(g), std::plus<>{} );
  }
  template<class G>
  friend auto operator-( alg_fun<F> f, alg_fun<G> g ) {
    return bin_op( std::move(f), std::move(g), std::minus<>{} );
  }
  template<class G>
  friend auto operator*( alg_fun<F> f, alg_fun<G> g ) {
    return bin_op( std::move(f), std::move(g),
      std::multiplies<>{} );
  }
  template<class G>
  friend auto operator/( alg_fun<F> f, alg_fun<G> g ) {
    return bin_op( std::move(f), std::move(g),
      std::divides<>{} );
  }

  template<class Rhs,
    std::enable_if_t< std::is_convertible<alg_fun<Rhs>, F>{}, bool> = true
  >
  alg_fun( alg_fun<Rhs> rhs ):
    F(std::move(rhs))
  {}

  // often doesn't compile:
  template<class G>
  alg_fun& operator-=( alg_fun<G> rhs )& {
    *this = std::move(*this)-std::move(rhs);
    return *this;
  }
  template<class G>
  alg_fun& operator+=( alg_fun<G> rhs )& {
    *this = std::move(*this)+std::move(rhs);
    return *this;
  }
  template<class G>
  alg_fun& operator*=( alg_fun<G> rhs )& {
    *this = std::move(*this)*std::move(rhs);
    return *this;
  }
  template<class G>
  alg_fun& operator/=( alg_fun<G> rhs )& {
    *this = std::move(*this)/std::move(rhs);
    return *this;
  }
};
template<class F>
alg_fun<F> make_alg_fun( F f ) { return {std::move(f)}; }

auto identity = make_alg_fun([](auto&& x){ return decltype(x)(x); });
template<class X>
auto always_return( X&& x ) {
  return make_alg_fun([x=std::forward<X>(x)](auto&&... /* ignored */) {
    return x;
  });
}

I think that about does it.

auto square = identity*identity;

we can also have type-erased alg funs.

template<class Out, class...In>
using alg_map = alg_fun< std::function<Out(In...)> >;

these are the ones that support things like *=. alg_fun in general don't type erase enough to.

template<class Out, class... In>
alg_map<Out, In...> pow( alg_map<Out, In...> f, std::size_t n ) {
  if (n==0) return always_return(Out(1));
  auto r = f;
  for (std::size_t i = 1; i < n; ++i) {
    r *= f;
  }
  return r;
}

could be done more efficiently.

Test code:

auto add_3 = make_alg_fun( [](auto&& x){ return x+3; } );
std::cout << (square * add_3)(3)  << "\n";; // Prints 54, aka 3*3 * (3+3)

alg_map<int, int> f = identity;
std::cout << pow(f, 10)(2) << "\n"; // prints 1024

Live example.

Here is a more efficient pow that works without type erasure:

inline auto raise(std::size_t n) {
  return make_alg_fun([n](auto&&x)
    -> std::decay_t<decltype(x)>
  {
    std::decay_t<decltype(x)> r = 1;
    auto tmp = decltype(x)(x);

    std::size_t bit = 0;
    auto mask = n;
    while(mask) {
      if ( mask & (1<<bit))
        r *= tmp;
      mask = mask & ~(1<<bit);
      tmp *= tmp;
      ++bit;
    }
    return r;
  });
}
template<class F>
auto pow( alg_fun<F> f, std::size_t n ) {
  return compose( raise(n), std::move(f) );
}

Live example. It uses a new function compose in alg_fun:

  template<class G>
  friend auto compose( alg_fun lhs, alg_fun<G> rhs ) {
    return make_alg_fun( [lhs=std::move(lhs), rhs=std::move(rhs)](auto&&...args){
        return lhs(rhs(decltype(args)(args)...));
    });
  }

which does compose(f,g)(x) := f(g(x))

Your code now literally becomes

alg_fun<Helper> h;
alg_fun<F> f;

auto result = pow( h, 10 )*f;

which is h(x)*h(x)*h(x)*h(x)*h(x)*h(x)*h(x)*h(x)*h(x)*h(x)*f(x). Except (with the efficient version) I only call h once and just raise the result to the power 10.

Given two functions, f(x) and g(y), compose will give us h(y) = compose(f,g) = f(g(y)). Note the use of static asserts to enforce the use of unary functions as well as to determine the argument type for the returned function. I will be choosing operator* as my composition operator. Thanks for the fun question, Gabriel of year 2013. Here is a solution. It works in c++14. #include <functional> #include <iostream> using std::function; // binary function composition for arbitrary types template <class F, class G> auto compose(F f, G g){ return [f,g](auto x){return f(g(x));}; } // for convienience template <class F, class G> auto operator*(F f, G g){ return compose(f,g

The process ∂{a,b} (a ∥ b) is equal to c. Axioms that describe the parallel composition operator are in Table 8. In this table the communications between action  C -= A is equivalent to C = C - A Multiply AND assignment operator. It multiplies the right operand with the left operand and assigns the result to the left operand.

Since the composition operator is an infix operator we can imitate this in C# with extension methods. Here is the composition function in C#:. Given a function g, the composition operator C g is defined as that operator which maps functions to functions as = ∘. Composition operators are studied in the field of operator theory. In programming languages

We compute the C*-algebra generated by a group of composition operators acting on certain reproducing kernel Hilbert spaces over the disk, where the symbols  Inherit a new class called C from A, and create a member object of B in C, but do not create a constructor for C. Create an object of class C and observe the results. Create a three-level hierarchy of classes with default constructors, along with destructors, both of which announce themselves to cout .

Comments
  • to have h(x)*h(x)*f(x), you have to change to have h1(x) = h(x)*h(x) and use ApplyOp<Helper1> A(h1);.
  • Use templates and template specialization
  • @Jarod42 that's somewhat missing the point. I want a more general solution that doesn't depend on the particular form of the operator.
  • @user9335240 I'm not sure I see how specialization helps - can you explain a little more?
  • @Jarod42 You can make a template function that has a template parameter of an int, that recursively resolves to the same function but with the template parameter subtracted by one, and make a specialization when this parameter == 2 that does the binding
  • This is extremely close to what I need. I tried to implement it in my project and it's not quite working - for some reason, the lambda returned by binder isn't capturing the correct behavior. If I do auto g = [&] (double x){return A(f,x);}; then evaluate A(g,x), I get the correct result, but not if I use auto g = binder<2,double>(A,f). It works brilliantly for the example I gave (your code works), but when I make the change to my ApplyOp it breaks. I may post a separate question as it's difficult to explain in a comment. Thanks!
  • OK, this turned out to be exactly what I needed. I needed to capture by value when returning the lambda expression (i.e. use [=]), and make sure all my operator() were const. Great solution, thanks again!