Function Composition

The usefulness of higher order functions is hard to dispute, you can safely and easily write functions which combine the functionality of other functions. The most basic of higher order functions is function composition, the topic of this post.

There is no standard way to compose functions, especially since there is no standard way to resolve a function’s argument and return types. Good thing that we have function traits! I will also be making use of the generalized function evaluation discussed previously.

To keep the discussion simple, I will only discuss unary functions, though conceivably one could make some clever use of std::forward_as_tuple and make a very complete and complex implementation.

Let’s start with the basics:

#include <functional>

#include "eval.h"
#include "function_traits.h"

template<class F, class G>
auto compose(F&& f, G&& g)
    -> std::function<typename function_traits<F>::return_type(
        typename function_traits<G>::template argument<0>::type)>
{
    using F_traits = typename function_traits<F>;
    using G_traits = typename function_traits<G>;

    static_assert(F_traits::arity == 1, "error: only unary functions can be composed.");
    static_assert(G_traits::arity == 1, "error: only unary functions can be composed.");

    using Arg = typename G_traits::template argument<0>::type;

    return [=](Arg arg){return eval(f,eval(g,arg));};
}

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.

The trailing return type uses the function_traits to cast the lambda to a valid function object. In c++14, the return type can be omitted entirely, and frankly it’s a huge improvement. Just look at that thing.

An example of this in action:

#include <iostream>

int main()
{
    auto double_then_add_three = compose(
        [](int n){return n+3;},
        [](int n){return n*2;}
    );

    for (unsigned i = 0; i < 10; ++i)
        std::cout << double_then_add_three(i) << " ";

    return 0;
}

Which outputs as expected:

3 5 7 9 11 13 15 17 19 21

Let’s try making an operator version of this. I will be choosing operator* as my composition operator.

template<class F, class G>
auto operator*(F&& f, G&& g)
{
    return compose(std::forward<F>(f),std::forward<G>(g));
}

This works quite well, until we try and combine function pointers.

#include <iostream>

int add_one(int n){return n+1;}
int times_two(int n){return n*2;}

int main()
{
    // fine
    auto double_then_add_three = [](int n){return n+3;} * [](int n){return n*2;};

    // error!
    auto double_then_add_one = &add_one * &times_two;

    return 0;
}

This is because the compiler is trying to multiply the two pointers and that makes absolutely no sense. How can we get around this? We can write our own custom operators. (I feel really bad about this! Don’t hate me!)

First we have to wrap our pointer in another object, we also add a test to see if a type is a wrapper:

template<class T>
struct wrapper
{
    wrapper(T t):value(t){};

    T value;
};

template<>
struct wrapper<void>
{};

template<class T>
struct is_wrapper
{
    enum{ value = false };
};

template<class T>
struct is_wrapper<wrapper<T>>
{
    enum{ value = true };
};

Now for the new composition operator, very similar but with some minor changes:

template<
    class F, class G,
    class = typename std::enable_if<!is_wrapper<F>::value>::type
    >
auto operator*(F&& f, G&& g)
{
    return compose(std::forward<F>(f),std::forward<G>(g));
}

template<class T>
auto operator*(T&& t, wrapper<void> v)
{
    return wrapper<T>(std::forward<T>(t));
}

template<class T, class F>
auto operator*(wrapper<T>&& t, F&& f)
{
    return compose(t.value,f);
}

#define COMPOSE * wrapper<void>() *

We can now use the macro COMPOSE as an operator which behaves exactly like compose. The macro causes the left operand to be placed in a wrapper, which then can be passed to the compose operator.

This workaround also works for objects which have their own operator* but it’s not pretty and will definitely raise some flags if you use this in production.

The end result is quite nice though, and you can see this for yourself:

#include <iostream>

int increment(int n){return n+1;}
int times_two(int n){return n*2;}

int main()
{
    auto double_then_add_three = [](int n){return n+3;} * [](int n){return n*2;};
    std::cout << double_then_add_three(20) << " ";

    auto echo = [](const std::string& s){return s+" "+s;};
    auto echo_length = &std::string::size * echo;
    std::cout << echo_length("hello") << " ";

    auto some_func = &increment COMPOSE &times_two COMPOSE &increment COMPOSE &increment;
    std::cout << some_func(-4);

    std::cout << "\n";
}

Which gives the output:

43 11 -3
Advertisements

3 comments

  1. ciber

    // g++ -std=c++1y composition.cpp

    #include

    using namespace std;

    // ———————————————————
    // ———————————————————
    template
    class Composite;

    // ———————————————————
    // ———————————————————
    template
    Composite compose2 (F1 f, F2 g) {
    return Composite {f,g};
    }

    // ———————————————————
    // ———————————————————
    template
    auto compose (F1 f, F2 g) -> decltype(compose2 (f, g))
    {
    return compose2 (f, g);
    }

    template
    decltype(auto) compose (F1 f, Fs … args)
    {
    return compose2 (f, compose(args…));
    }

    // ———————————————————
    // ———————————————————
    template
    class Composite{
    private:
    F1 f1;
    F2 f2;

    public:
    Composite(F1 f1, F2 f2) : f1(f1), f2(f2) { }

    template
    auto operator() (IN i) -> decltype(f2(f1(i)))
    {
    return f2 ( f1(i) );
    }
    };

    // ———————————————————
    // ———————————————————
    int f(int a) { return 2*a; }

    double g(int a) { return a+2.5; }

    double h(double a) { return 2.5*a; }

    double i(double a) { return 2.5-a; }

    class Functor {
    double x;

    public:

    Functor (double x_) : x(x_) { }

    double operator() (double a) { return a*x; }
    };

    // ———————————————————
    // ———————————————————
    int main () {

    auto l1 = [] (double a) { return a/3; };
    auto l2 = [] (double a) { return 3.5+a; };

    Functor fu {4.5};

    auto compos1 = compose (f, g, l1, g, h, h, l1, l2);

    auto compos2 = compose (compos1, l1, l2, fu);

    auto x = compos2 (3);

    cout << x << endl;
    cout << compos2(3) << endl;

    cout << fu(l2(l1(l2(l1(h(h(g(l1(g(f(3))))))))))) << endl;

    } // ()

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s