Monday, September 3, 2012

Function Composition in C++

Function composition can be achieved in C++ very similarly to partial application. First, what is it?

In Haskell, one can write something like f . g, meaning the composition of f and g. It produces a function, h, such that h(x) = f( g(x) ). Since Haskell uses curried notation, if f takes two arguments, then h would be defined h(x,y) = f( g(x), y ). Composition becomes especially useful when we can express a chain of function calls with it. For example this...

    auto y = f(x);
    auto z = g(y);
    auto a = h(z);

...could be rewritten like so, using Haskell notation:

    auto a = (h . g . f)(x);

As with partial application, one might first think of writing compose as a lambda function, but we don't know the type of the arguments. Instead, we create a type that holds f and g.

    template< class F, class G > struct Composition {
        F f;
        G g;

        template< class _F, class _G >
        constexpr Composition( _F&& f, _G&& g ) : f( forward<_F>(f) ), g( forward<_G>(g) ) { }

        template< class X, class ...Y >
        decltype( f( g(declval<X>()), declval<Y>()... ) )
        operator() ( X&& x, Y&& ...y ) {
            return f( g(forward<X>(x)), forward<Y>(y)... );
        }
    };

    template< class F, class G, class C = Composition<F,G> >
    constexpr C compose( F f, G g ) {
        return C( move(f), move(g) );
    }

We can now very simply define a:

    auto a = compose( h, compose(g,f) )(x);
    auto b = compose( compose(h,g) f )(x); // Equivalently

Composition really doesn't get more complicated than that. We can implement a few different versions for slightly different purposes, but that's about it. Still, this adds flexibility, so let's look at some others. Each requires writing its own Composition class, but i'll just briefly go over the different ways to look at compositions.

First, i should note that the GCC extends the standard by adding compose1 and compose2. compose1 acts on unary functions (like f(x)), however it is unlike the the above compose in that it expects f to take only one argument (the return of g(x)). compose2 does something more interesting. Consider this:

    typedef std::pair<int,int> vec;
    int& vec_x( vec& v ) { return v.first; }
    int& vec_y( vec& v ) { return v.second; }

    auto sum_of_elements = __gnu_cxx::compose2( std::plus<int>(), vec_x, vec_y );
    int five = sum_of_elements( std::make_pair(2,3) );

compose2 takes one binary function (in this case, +), and two unary functions and produces a unary function. sum_of_elements(v) = vec_x(v) + vec_y(v). This is not standard, however, so implementing our own version makes sense for portability. I might rename this function to bcompose for "binary composition".

Our regular compose function expects a n-ary f and a unary g. Wouldn't a version expecting a unary f and n-ary g be helpful? I would call this mcompose.

At the end of the day, if a composition does not exists that perfectly meats one's needs, it can be trivially implemented.