Function Composition in C++

Question

There are a lot of impressive Boost libraries such as Boost.Lambda or Boost.Phoenix which go a long way towards making C++ into a truly functional language. But is there a straightforward way to create a composite function from any 2 or more arbitrary functions or functors?

If I have: int f(int x) and int g(int x), I want to do something like f . g which would statically generate a new function object equivalent to f(g(x)).

This seems to be possible through various techniques, such as those discussed here. Certainly, you can chain calls to boost::lambda::bind to create a composite functor. But is there anything in Boost which easily allows you to take any 2 or more functions or function objects and combine them to create a single composite functor, similar to how you would do it in a language like Haskell?

Answer 1

To anyone stumbling onto this page, there's a great blog post on this subject from bureau14:

http://blog.quasardb.net/function-composition-in-c11/

This takes advantage of the new features in C++ 11 as well as using boost.

Answer 2

C++11. No boost. No helper classes. Any amount of arguments. Just std::function and variadic templates.

template <typename F1, typename F2>
struct function_composition_traits : public function_composition_traits<decltype(&F1::operator()), decltype(&F2::operator())>
{};

template <typename ClassType1, typename ReturnType1, typename... Args1, typename ClassType2, typename ReturnType2, typename... Args2>
struct function_composition_traits<ReturnType1(ClassType1::*)(Args1...) const, ReturnType2(ClassType2::*)(Args2...) const>
{
        typedef std::function<ReturnType2(Args1...)> composition;

        template <typename Func1, typename Func2>
        inline static composition compose(const Func1& f1, const Func2& f2) {
            return [f1,f2](Args1... args) -> ReturnType2 { return f2(f1(std::forward<Args1>(args)...)); };
        }
};

template <typename F1, typename F2>
typename function_composition_traits<F1,F2>::composition compose(const F1& lambda1,const F2& lambda2)
{
        return function_composition_traits<F1,F2>::template compose<F1,F2>(lambda1, lambda2);
}

template <typename F, typename... Fs>
auto compose(F f, Fs... fs) -> decltype(compose(f, compose(fs...)))
{
        return compose(f, compose(std::forward<Fs>(fs)...));
}

Usage:

auto add = [](int x, int y){ return x+y; };
auto mul = [](int x){ return x*2; };
auto divide = [](int x) { return (double)x / 3.0; };
auto test = compose(add, mul, divide);

cout << "Result: " << test(2,3);

Output:

Result: 3.33333

Answer 3

See this answer https://stackoverflow.com/a/27727236/286335. Really short, easy and general.

Answer 4

Stumbling upon this question, I'd like to point out to anyone who comes across this today that this is possible with a relatively elegant syntax using just the standard library and a few helper classes thanks to decltype, auto, and perfect forwarding.

Defining these two classes:

template <class Arg, class ArgCall, class OuterCall>
class pipe {
private:
    ArgCall argcall;
    OuterCall outercall;
public:
    typedef pipe<Arg, ArgCall, OuterCall>  this_type;
    pipe(ArgCall ac, OuterCall oc) : argcall(ac), outercall(oc) {}
    auto operator()(Arg arg) -> decltype(outercall(argcall(arg))) {
        return outercall(argcall(arg));
    }
    template <class NewCall>
    pipe<Arg, this_type, NewCall> operator[](NewCall&& nc) {
        return {*this, std::forward<NewCall>(nc)};
    }
};

template <class Arg>
class pipe_source {
public:
    typedef pipe_source<Arg> this_type;
    Arg operator()(Arg arg) {
        return arg;
    }
    template <class ArgCall, class OuterCall>
    static pipe<Arg, ArgCall, OuterCall> create(ArgCall&& ac, OuterCall&& oc) {
        return {std::forward<ArgCall>(ac), std::forward<OuterCall>(oc)};
    }
    template <class OuterCall>
    pipe<Arg, this_type, OuterCall> operator[](OuterCall&& oc) {
        return {*this, std::forward<OuterCall>(oc)};
    }
};

A simple program:

int f(int x) {
        return x*x;
}

int g(int x) {
        return x-2;
}

int h(int x) {
        return x/2;
}

int main() {
        auto foo = pipe_source<int>::create(f, g);
        //or:
        auto bar = pipe_source<int>()[g][h];
        std::cout << foo(10) << std::endl;
        std::cout << bar(10) << std::endl;
        return 0;
}

This has the added benefit that once it's in a pipe, as long as the return type is correct you can add another function f to the chain with pipe[f].

Then:

$ g++ test.cpp -o test -std=c++11
$ ./test
98
4
$

Answer 5

Template them.

template<typename T1> class FunctorOne {
    FunctorOne(T1 newt)
        : t(newt) {}
    void operator()() {
        t();
    }
    T1 t;
};
template<> class FunctorOne<void> {
    void operator()() {
    }
};
template<typename T1> class FunctorTwo {
    FunctorOne(T1 newt)
        : t(newt) {}
    void operator()() {
        t();
    }
    T1 t;
};
template<> class FunctorTwo<void> {
    void operator()() {
    }
};
FunctorOne<FunctorTwo<FunctorOne<FunctorTwo<void>>>>> strangefunctionobject(FunctorTwo(FunctorOne(FunctorTwo()));

Excellent use of typedefs is recommended.
Edit: Whoops. Turns out that type inference in constructors sucks. I'll get back in a minute with something that actually works :P
Even more edit:
If you wanted just functors rather than functionoids, you could just create a new instance, or even just use static functions.

template<typename T1, typename T2> class FunctorOne {
public:
    static bool Call() {
        T1::Call(T2::Call());
        return true;
    }
};
template<> class FunctorOne<void, void> {
public:
    static bool Call() {
    }
};
template<typename T1> class FunctorTwo {
public:
    static bool Call() {
        T1::Call();
    }
};
template<> class FunctorTwo<void> {
public:
    static bool Call() {
    }
};

bool haicakes = FunctorOne<FunctorTwo<void>, FunctorTwo<void>>::Call();

This assumes that in any given function, you can handle each different signature somewhat manually. Use of decltype could help in this regard with a C++0x compiler.

Answer 6

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.