11
\$\begingroup\$

Given a number of functions f1, f2, f3, ..., fn I want to create a composite function g so that g(x) calls f1(f2(f3(...(fn(x)))).

I came across a blog post which was mentioned in a related Stack Overflow question.

These solutions seem to be very involved. In my own code, I am using a very simple recursion of std::bind instead.

#pragma once

#include <functional>

// TODO: C++14: remove traits and use auto return type deduction

// traits to infer the return type of recursive binds
template<typename... Fn>
struct composite_function_traits;

// bind a single function with a placeholder
template<typename F1>
struct composite_function_traits<F1> { typedef decltype(std::bind(std::declval<F1>(), std::placeholders::_1)) type; };

template<typename F1>
typename composite_function_traits<F1>::type make_composite_function(F1&& f1)
{
    return std::bind(std::forward<F1>(f1), std::placeholders::_1);
}

// recursively bind multiple functions
template<typename F1, typename... Fn>
struct composite_function_traits<F1, Fn...> { typedef decltype(std::bind(std::declval<F1>(), std::declval<typename composite_function_traits<Fn...>::type>())) type; };

template<typename F1, typename... Fn>
typename composite_function_traits<F1, Fn...>::type make_composite_function(F1&& f1, Fn&&... fn)
{
    return std::bind(std::forward<F1>(f1), make_composite_function(std::forward<Fn>(fn)...));
}

Are there advantages to the more complex methods for function composition?

\$\endgroup\$
1
\$\begingroup\$

A very interesting question. I can identify two main differences between your implementation (using variadic templates) and the linked article's implementation (using Boost.Fusion):

  1. The definition of function composition. A call to your make_composite_function(f1, f2, f3)(x) is semantically equivalent to f1(f2(f3(x))). Calling the linked article's compose(f1, f2, f3) is semantically equivalent to f3(f2(f1(x))).

    Which definition is more natural is completely up to the reader. Both are perfectly valid. Your make_composite_function has the nice property that it is very easy to implement with variadic templates (since the recursion uses "pop front" logic). This is actually mentioned as an alternative in the linked article.

    Furthermore, they argue for their definition of function composition because it follows the reading direction. E.g., compose(receive, decode, store)(data) is semantically equivalent to store(decode(receive(data))) which follows the expected behaviour of first receiving data, then decoding it, and finally storing it. To get the same semantics with your definition, we would have to write make_composite_function(store, decode, receive). Again, this does the same thing but is arguably harder to decipher during a cursory read-through.

    Alas, the linked article goes through a world of trouble to get that "pop back" recursion logic to work (using Boost.Fusion). So they do as they do not because they are oblivious of variadic templates but because variadic recursion simply doesn't cut it. Here's a quote from the article:

    Variadic templates unfortunately work in a "pop front" logic, making the code actually much less straightforward (because these unintelligible recursive preprocessor macros are obviously mundane). You could nevertheless write a pop front variadic template version with an adapter that reverses the list of parameters.

    Note the proposed alternative implementation using a reversion adaptor. That would be a nice C++ exercise. I wonder how that would compare complexity-wise.

  2. The linked article's implementation supports std::tuple arguments such as compose(std::make_tuple(f1, f2, f3)). Yours don't. Of course, this adds extra complexity to their implementation compared to yours. There's not much more to say on this point.

To sum up, the difference in complexity is because you seek different interfaces. Both interfaces are valid and work. Which one is more natural depends on the application.

Edit: Here is a code sample of your version. Note that I just use auto return type deduction (as you suggested yourself in the code comment).

\$\endgroup\$
  • \$\begingroup\$ Great observations. I was going for the usual mathematical notation. If indeed the added complexity is to write the functions in "causal order" I am now perfectly content to use the simpler version. \$\endgroup\$ – user56427 Nov 5 '14 at 15:40
  • \$\begingroup\$ @Nicolas, I'm glad you like the answer. I personally prefer your simply version as well. C++14's auto return type deduction makes it very simple yet powerful. Good idea with this function. Cheers! \$\endgroup\$ – Frederik Aalund Nov 5 '14 at 19:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy