Folding Functions

In the last post we looked at basic usage of C++17 Fold Expressions. I found that many posts on this topic discuss simple types and ignore how folds may be applicable to more complex types as well. [Edit: Please see the comments section for some examples elsewhere in the blogosphere.] In this post I'm going to describe folding over functions.

Composing Functions

Function composition is a powerful way of creating complex functions from simple ones. Functions that accept a single argument and return a value are easily composable. Consider the following example to compose two std::functions.

template <class A, class B, class C>
std::function<C(A)> compose(std::function<B(A)> f, std::function<C(B)> g)
{
  return [=](A a) -> C { return g(f(a)); };
}

int main(void)
{
    std::function<int(std::string)> to_num = [](std::string s) { return atoi(s.c_str()); };
    std::function<bool(int)> is_even = [](int i) { return i%2==0; };
    auto is_str_even_num = compose(to_num, is_even);
    std::cout << std::boolalpha << is_str_even_num("1234"); // prints true
}

Function compose accepts two std::function arguments and returns another one. The types of these std::function arguments are important. f is a function from A->B where as g is a function from B->C. Therefore, it makes sense that compose can generate another function of type A->C. The output f goes to the input of g. The implementation of the lambda confirms that.

As std::function is kind of verbose and not very idiomatic in C++ when you want to pass functions around. I'll try to use C++11 lambdas initially. I want to stay away from generic lambdas because argument and return types are kinda important. In generic lambdas, however, it's impossible to find their argument and return types without knowing an actual argument or its type. Note that in compose function we have access to functions only and no arguments.

Lets rewrite compose to accepts lambdas.

template <class F, class G>
auto compose(F&& f, G&& g)
{
  using ArgType    = detail::arg_type_t<F>;
  using ResultType = detail::result_type_t<G>;  
  return [f,g](ArgType a) -> ResultType { return g(f(a)); };
}

F and G are generic arguments, which we expect to be non-generic lambdas. We extract the argument type of F and result type of G and return a composition of two lambdas satisfying the type signature.

This implementation is not very idiomatic. Extracting the argument and return types of functions in this style is falling out of favor. std::function::argument_type and std::function::result_type have been deprecated in C++17. A more idiomatic way would have been to return a generic lambda without bothering the argument type. C++ clearly wants to favor duck-typing at compile-time. Until we've concepts in the language, of course.

I'll skip the implementation of the detail namespace. It's in the same vein as this stackoverflow answer.

Folding Functions

Folding functions is a generalization of function composition applied to fold expressions. First, we need to pick up an operator to use fold expressions with. I like >> as it's quite intuitive. Here's the earlier function implemented as an overloaded operator.

template <class F, class G>
auto operator >>(F&& f, G&& g)
{
  using ArgType    = detail::arg_type_t<F>;
  using ResultType = detail::result_type_t<G>;  
  return [f,g](ArgType a) -> ResultType { return g(f(a)); };
}

We'll now write a new compose function that uses a fold expression over function types. Of course, it's going to use the overloaded >> operator.

template <class... Funcs>
auto compose(Funcs... funcs)
{
   return (... >> funcs);   
}

The earlier main program will work just fine with this new implementation of compose. It works with lambdas too.

auto to_num = [](std::string s) { return atoi(s.c_str()); };
auto is_even = [](int i) { return i%2==0; };
auto is_str_even_num = compose(to_num, is_even);
std::cout << std::boolalpha << is_str_even_num("1234") << "\n"; // prints true

Interestingly, this compose function works fine with a single argument as it simply returns the argument as discussed in the previous post. It does not work with empty parameter pack however. What could we return when we get an empty parameter pack? In other words what would be the identity for the function type? Well, it's just a function that returns its argument. Let's see it in action using a binary fold.

struct Identity
{
  template <class T>
  T operator()(T&& t) { return std::forward<T>(t); }
};

template <class... Funcs>
auto compose(Funcs... funcs)
{
   return (Identity() >> ... >> funcs);   
}

Only problem, however, is that it does not compile. Not that anything is wrong with binary folds but the overloaded >> for generic functions cannot digest Identity. Identity has a generic function call operator. There's no way to get it's argument_type and result_type without knowing the type of the argument. The compose function does not have it.

We're therefore forced to use a generic implementation of operator >>.

template <class F, class G>
auto operator >>(F&& f, G&& g)
{
  return [f,g](auto a) { return g(f(a)); };
}

With this final variation, functions can be folded over in a binary fold expression.

I will conclude this blog post with a bit of monoid theory.

You might wanna ask yourself if function composition is another monoid? As it turns out, it is. It makes sense intuitively. Composition of two functions give rise to another function. The composition is also associative. It does not matter if we call compose(f, compose(g,h)) or compose(compose(f,g),h). The end result is the same. Squint a little and you will realize that they are just left and right folds. Finally, there's also an identity function, which when combined with any other function makes no observable difference. Therefore, we can say that function form a monoid under composition.

Next time we'll look at even more interesting functions---those return values wrapped a generic "container".