Continuation Passing Style

Let’s take a break from type classes and take a brief look at one of the more esoteric concepts of functional programming. Continuation passing style (CPS) is a method of programming which allows for intricate manipulation of control flow while still maintaining functional purity.

Continuations can be used to implement a whole range of things from exceptions to coroutines, but today we’ll just introduce them and a few interesting and useful concepts.

Suppose we have a show function which just prints things to the screen.

auto show = [](const auto& v){std::cout << v << "\n";};

Typically we deal with calling functions, storing and modifying return values, then passing those values on to the next functions:

auto make_one = [](){return 1;};

// prints 1
show(make_one());

In CPS, functions have an extra argument which is what handles the result. This is the continuation, named “k” by convention.

auto one_cont = [](auto&& k){return k(1);};

// Also prints 1
one_cont(show);

The one_cont takes a function as an argument and calls it with what would normally have been the return value. Note that it is written as a generic lambda, this is because we want to pass any type of function while avoiding “unresolved overloaded function” errors.

Other functions can be converted into CPS in a rather straightforward way:

auto add_cont = []<class T>(const T& lhs, const T& rhs, auto&& k)
{
    return k(lhs+rhs);
};

auto sub_cont = []<class T>(const T& lhs, const T& rhs, auto&& k)
{
    return k(lhs-rhs);
};

auto mul_cont = []<class T>(const T& lhs, const T& rhs, auto&& k)
{
    return k(lhs*rhs);
};

auto div_cont = []<class T>(const T& lhs, const T& rhs, auto&& k)
{
    return k(lhs/rhs);
};

auto eq_cont = []<class T>(const T& lhs, const T& rhs, auto&& k)
{
    return k(lhs==rhs);
};

// etc...

add_cont(1,2,show); // prints 3
times_cont(3,4,show); // prints 12

More intricate functions can be written combining other CPS functions, for example this function which returns the sum of the squares of two numbers:

auto sum_of_squares_cont = [&]<class T>(const T& lhs, const T& rhs, auto&& k)
{
    return mul_cont(lhs,lhs,[&](const T& lhs2){
            return mul_cont(rhs,rhs,[&](const T& rhs2){
                return add_cont(lhs2,rhs2,k);
            });
        });
};

That’s quite a mess, let’s break it down by unwrapping it layer by layer. The outermost layer is a call to mult_cont which is used to square the left number:

return mul_cont(lhs,lhs,
        // ...
    );

The next layer is the continuation of the first layer:

[&](const T& lhs2){
    return mul_cont(rhs,rhs,
        // ....
    }

As with the outer layer, we are using mul_cont to square the right number.

Additionally, as the continuation of the first layer, we receive the argument lhs2. Now this is a clever trick, by passing it as the argument, we can access the result of the first computation by name despite never actually storing in a variable.

Note: We will be using this trick quite often in the future!

The last layer uses the trick as well:

[&](const T& rhs2){
        return add_cont(lhs2,rhs2,k);
    }

We capture lhs2 and finally compute the sum of the squares using add_cont. As this is the final result of the computation, the continuation is that of the entire sum_of_squares_cont function.

The function can then be used as expected:

sum_or_squares_cont(3,4,show); // prints 25

You can even write recursive functions using CPS! This rather hard to do generically, since resolving the templates will involve an infinite loop, but it’s possible to get something together:

std::function<void(int,const std::function<void(int)>&)> factorial_cont =
    [&](int n, const std::function<void(int)>& k){
        eq_cont(n,0,[&](bool done){
                if (done)
                    k(1);
                else
                    sub_cont(n,1,[&](int m){
                            factorial_cont(m,[&](int p){
                                    mul_cont(n,p,k);
                                });
                        });
            });
    };

Overall, continuation passing style is a pretty radical departure from the conventional way of programming and the next few posts will explore what can be done with these functions.

P.S. This stuff is pretty heavy on the lambda functions. Here is a good introduction to what you can do with lambda calculus.

Type Class – Filterable

Mapping is about preserving structure while changing values. Folding is about destroying structure. But what about filtering, what does it mean to filter?

Like folding, filtering destroys the original structure but it rebuilds the structure after removing undesired elements. It seems then, that filtering might be a special case of folding. For example:

int main()
{
    std::vector<int> numbers{0,1,2,3,4,5,6,7,8,9,10};

    // filter using lfold
    auto append_even = [](std::vector<int> ns, int n)
    {
        if (n % 2 == 0) ns.push_back(n);
        return ns;
    };

    for (int n : lfold(append_even,std::vector<int>{},numbers))
        std::cout << n << " ";

    return 0;
}

Output:

0 2 4 6 8 10

Another way to look at filtering is to think of each element as a single element list. Filtering then becomes a matter of transforming the lists into empty ones then using fold to recombine the lists:

int main()
{
    std::vector<int> numbers{0,1,2,3,4,5,6,7,8,9,10};

    // filter using map and fold
    auto to_even_vector = [](int n){
        if (n % 2 == 0)
            return std::vector<int>{n};

        return std::vector<int>{};
    };

    for (int n : fold(map(to_even_vector,numbers)))
        std::cout << n << " ";
}

Note that this fold uses monoid to get the aggregator and seed value for a vector. We’re not going to require that filterable inherit from monoid, since that would exclude things like the upcoming std::optional but it’s an recurring idea. In haskell, mfilter actually treats Maybe, the equivalent of optional, as a monoid.

In addition to being foldable, a filterable needs to be structuraly simple enough that it can be rebuilt by appending new values; filtering a binary tree wouldn’t make much sense. This can be seen in the haskell type class ListLike, which provides filtering and inherits from both monoid and a version of foldable.

We define filterable like this:

template<class T>
struct filterable // : foldable
{
    // Type value_type
    // filterable<A> filter(bool(A),filterable<A>)
    static constexpr bool is_instance = false;
};

// Convenience function
template<class F, class T>
auto filter(F&& f, const T& in)
{
    return filterable<T>::filter(std::forward<F>(f),in);
}

Defining the stl container instances:

// container instances
template<class T>
struct default_container_filterable : public foldable<T>
{
    // Type value_type
    using value_type = typename container_traits<T>::value_type;

    // filterable<A> filter(bool(A),filterable<A>)
    template<class F>
    static auto filter(F&& f, const T& in) -> T
    {
        T out;

        for (auto& a : in)
            if (eval(f,a))
                container_traits<T>::add_element(out,a);

        return out;
    }

    static constexpr bool is_instance = false;
};

#define FC_DEFAULT_CONTAINER_FILTERABLE(T)\
    template<class... Args>\
    struct filterable<T<Args...>> : public default_container_filterable<T<Args...>>\
    {};

FC_DEFAULT_CONTAINER_FILTERABLE(std::deque);
FC_DEFAULT_CONTAINER_FILTERABLE(std::list);
FC_DEFAULT_CONTAINER_FILTERABLE(std::multiset);
FC_DEFAULT_CONTAINER_FILTERABLE(std::set);
FC_DEFAULT_CONTAINER_FILTERABLE(std::basic_string);
FC_DEFAULT_CONTAINER_FILTERABLE(std::unordered_multiset);
FC_DEFAULT_CONTAINER_FILTERABLE(std::unordered_set);
FC_DEFAULT_CONTAINER_FILTERABLE(std::vector);

For the sake of efficiency, we don’t actually use fold in the implementation of filter.

Despite std::optional being a good candidate for filterable, we avoid making std::shared_ptr filterable. If the pointed value passes the filter, should filter return a pointer to the same value or a pointer to a copied value? There are compelling reasons for both and this seems like an area ripe for unexpected results, so let’s just go ahead and stay out of it.

Now that we have map, filter and fold, we can combine these to do all sorts of interesting operations on data. For example, this code will find the mean income of people in their 20s:

struct Person
{
    std::string name;
    int age;
    double income;
};

double mean_20s_income(const std::vector<Person>& people)
{
    auto in_20s = [](const Person& p){return p.age < 30 && p.age >= 20;};

    auto get_mean = [n=0](double last_mean, double income) mutable
    {
        ++n;
        return last_mean*(n-1)/n + (double)income/n;
    };

    return lfold(get_mean, 0.0, map(&Person::income, filter(in_20s, people)));
}

Of course, this could be done by storing the filtered list of incomes, but whatever! The possibilities are endless!

Complete code is available here. I would like to thank the friendly people at r/haskell for all their help.

Type Class – RFoldable

The foldable introduces the functions which aggregate values. The lfold, in particular, provides “forward” aggregation but the matching reverse aggregation is missing. This is because not every instance of foldable can be sensibly read in reverse, such as std::unordered_set.

Right folds are important in computer science since they can be seen as a structural substitution of cons with an aggregation function and that concept remains important even though we don’t work with just linked lists. rfoldable is an extension of foldable which provides this additional functionality:

template<class T>
struct rfoldable // : foldable
{
    // Type value_type
    // B rfold(B(A,B),B,foldable<A>)
    static constexpr bool is_instance = false;
};

// convenience functions
template<class F, class B, class T>
auto rfold(F&& f, B&& b, const T& in)
{
    return rfoldable<T>::rfold(std::forward<F>(f),std::forward<B>(b),in);
}

This demonstrates how type classes can be inherited much like the usual c++ class. Conceptually, it makes sense that something that can be folded from the right can also be folded from the left. Notice that the order of argument types in the function are switched: lfold is of type B(B,A) whereas rfold is of type B(A,B).

Foldable had the fold function which performed a left fold with seed and aggregation function provided by monoid. This is not duplicated in rfoldable since the monoid operator is associative. An equivalent function using a right fold would give the exact same result.

The implementation is straightforward:

// std::shared_ptr
template<class T>
struct rfoldable<std::shared_ptr<T>> : public foldable<std::shared_ptr<T>>
{
    // Type value_type
    using value_type = T;

    // B rfold(B(A,B),B,foldable<A>)
    template<class F, class B>
    static auto rfold(F&& f, B b, const T& in) -> B
    {
        if (in)
            b = ::fc::function::eval(f,b,*in);

        return b;
    }

    static constexpr bool is_instance = true;
};

// containers
template<class T>
struct default_container_rfoldable : public default_container_foldable<T>
{
    // Type value_type
    using value_type = typename ::fc::data::container_traits<T>::value_type;

    // B rfold(B(A,B),B,foldable<A>)
    template<class F, class B>
    static auto rfold(F&& f, B b, const T& in) -> B
    {
        for (auto a_it = in.begin(); a_it != in.end(); ++a_it)
            b = ::fc::function::eval(f,*a_it,b);

        return b;
    }

    static constexpr bool is_instance = true;
};

It is interesting to note that rfold and lfold can be implemented in terms of each other. For example, rfold can be written like this:

template<class T>
struct rfoldable<T> : public foldable<T>
{
    // ...

    // B rfold(B(A,B),B,foldable<A>)
    template<class F, class B>
    static auto rfold(F&& f, B b, const T& in) -> B
    {
        std::function<B(const B&)> identity = [](const B& b){return b;};
        auto reverser = [&](std::function<B(const B&)>& g, const value_type& a)
            -> std::function<B(const B&)>
        {
            return [&,g](const B& b){return g(f(a,b));};
        };

        return lfold(reverser,identity,in)(b);
    }

    // ...
};

Essentially, reverser transforms each element into a function which performs a single step of the aggregation. These functions are then composed using lfold and the result is called with the seed.

Conceivably, one could create a variadic fold which aggregates over multiple foldables at once. The complexity there is that unlike map, we now have a seed value and if we want some flexibility in the order of argument we now have to somehow specify which one is the seed.

Next time, we will introduce filtering, completing the trinity of map, filter and fold.

Edit: Didn’t even need generic lambdas!

Type Class – Foldable

The next type class to look at is foldable, which is based on the Foldable type class in Haskell. In addition to being quite useful, this type class is a good demonstration of the interactions between type classes.

Where mappable is about transformation, foldable is about aggregation. For example, mapping a vector will return a new vector with its values transformed, while folding a vector will return some combination of those values.

It might appear as though every foldable is also mappable and vice versa, but there are some exceptions. For example, you can’t aggregate every result of a function. Likewise, mapping a binary search tree might require changing the tree structure going beyond plain mapping.

To demonstrate folding, the following code would output the sum of numbers from 1 to 10:

// outputs: 55
std::vector<int> numbers{1,2,3,4,5,6,7,8,9,10};
std::cout << fold(numbers);

The operation used to combine them is determined by the monoid type class. This operation is addition for fundamental data types, concatenation for containers, multiplication for matrices, etc.

If a seed value or a customized aggregation function is needed, lfold can be used:

std::vector<int> letters{'h','e','l','l','o'};
auto build_string = [](const std::string& s, char c){return s+c;};

// outputs: !hello
std::cout << lfold(build_string,std::string("!"),letters) << "\n";

The definition of foldable can be written like this:

template<class T>
struct foldable
{
    // Type value_type
    // A fold(foldable<A>) requires monoid<A>
    // B lfold(B(B,A),B,foldable<A>)
    static constexpr bool is_instance = false;
};

// convenience functions
template<class T>
auto fold(const T& in)
{
    return foldable<T>::fold(in);
}

template<class F, class B, class T>
auto lfold(F&& f, B&& b, const T& in)
{
    return foldable<T>::lfold(std::forward<F>(f),std::forward<B>(b),in);
}

The lfold function is a left fold where objects are aggregated from the left or the “beginning”. In foldables like std::unordered_map, the actual order of aggregation is not consistent.

Notice that fold actually has a requirement that A is a monoid, alluding to the syntax of the future concepts lite. The idea is that if the value type is a monoid, a seed value and aggregation function can actually be obtained from the monoid type class.

We can see all of this put into play for the stl containers:

template<class T>
struct default_container_foldable
{
    // Type value_type
    using value_type = typename container_traits<T>::value_type;

    // A fold(foldable<A>) requires monoid<A>
    template<
        class T_,
        class = typename std::enable_if<std::is_same<T,T_>::value>,
        class = typename std::enable_if<
            monoid<typename container_traits<T_>::value_type>::is_instance
            >::type>
    static auto fold(const T_& in)
    {
        using A = typename ::fc::data::container_traits<T_>::value_type;

        return lfold(monoid<A>::append,monoid<A>::empty(),in);
    }

    // B lfold(B(B,A),B,foldable<A>)
    template<class F, class B>
    static auto lfold(F&& f, B b, const T& in) -> B
    {
        for (auto& a : in)
            b = ::fc::function::eval(f,b,a);

        return b;
    }

    static constexpr bool is_instance = true;
};

The mess of a template for fold is to keep the compiler from attempting to instantiate it if T doesn’t contain monoids.

We can actually also treat std::shared_ptr as a foldable if you think of it as a container that can hold 0 or 1 of something.

template<class T>
struct foldable<std::shared_ptr<T>>
{
    // Type value_type
    using value_type = T;

    // A fold(foldable<A>) requires monoid<A>
    template<
        class T_,
        class = typename std::enable_if<std::is_same<T,T_>::value>,
        class = typename std::enable_if<monoid<T>::is_instance>::type>
    static auto fold(const T_& in)
    {
        if (in)
            return monoid<T>::append(monoid<T>::empty(),*in);

        return monoid<T>::empty();
    }

    // B lfold(B(B,A),B,foldable<A>)
    template<class F, class B>
    static auto lfold(F&& f, B b, const std::shared_ptr<T>& in) -> B
    {
        if (in)
            b = eval(f,b,*in);

        return b;
    }

    static constexpr bool is_instance = true;
};

This could be potentially useful for avoiding null pointer accesses.

Combining mappable and foldable leads to some powerful possibilities. For example, if you want to get a list of names from a vector of people, you can do this:

struct person
{
    std::string name;
};

int main()
{
    std::vector<person> people{{"Robb"},{"Jon"},{"Sansa"},{"Brandon"},{"Arya"},{"Rickon"}};

    auto list_strings = [](const std::string& lhs,const std::string& rhs)
    {
        if (lhs.empty())
            return rhs;
        return lhs + ", " + rhs;
    };

    // get everyone's name then combine them with list_strings
    std::cout << lfold(list_strings,std::string(),map(&person::name,people));
    return 0;
}

Which produces a nicely formatted list of names:

Robb, Jon, Sansa, Brandon, Arya, Rickon

Full code is available here!

Zipper and other Function Objects

There are some useful function objects, which can be used with mappable.

Zippers and pairers pack things into tuples and pairs respectively:

struct zipper
{
    template<class... Args>
    auto operator()(Args&&... args)
    {
        return std::make_tuple(std::forward<Args>(args)...);
    }
};

struct pairer
{
    template<class L,class R>
    auto operator()(L&& l, R&& r)
    {
        return std::make_pair(std::forward<L>(l),std::forward<R>(r));
    }
};

If you need to pack constant values or references, you can use a variation on this concept. The pair variant is particularly useful for inserting values into std::map.

template<class... Args>
struct zipper_t
{
    template<class... Args_>
    auto operator()(Args_&&... args)
    {
        return std::tuple<Args...>(std::forward<Args_>(args)...);
    }
};

template<class L,class R>
struct pairer_t
{
    template<class L_,class R_>
    auto operator()(L_&& l, R_&& r)
    {
        return std::pair<L,R>(std::forward<L_>(l),std::forward<R_>(r));
    }
};

Following the nomenclature of std::make_pair and std::make_shared, make just makes an object. This is quite useful since you can’t get a pointer to a constructor.

template<class T>
struct make
{
    template<class... Args>
    auto operator()(Args&&... args)
    {
        return T(std::forward<Args...>(args...));
    }
};

Less type strict versions of std::plus and its siblings are useful for when you need to operate on different types, such as matrices and vertices.

#define FC_BINARY_OPERATORS\
    X(plus,+)\
    X(minus,-)\
    X(multiplies,*)\
    X(divides,/)\
    X(modulus,%)\
    X(equal_to,==)\
    X(not_equal_to,!=)\
    X(greater,>)\
    X(less,<)\
    X(greater_equal,>=)\
    X(less_equal,<=)\
    X(logical_and,&&)\
    X(logical_or,||)\
    X(bit_and,&)\
    X(bit_or,|)\
    X(bit_xor,^)

#define X(name,symbol)\
    struct name\
    {\
        template<class L,class R>\
        auto operator()(L&& l, R&& r)\
        {\
            return l symbol r;\
        }\
    };

FC_BINARY_OPERATORS
#undef X

There also exist functions unzip and unpair which are also members of mappable analogous to the Haskell unzip. For example, unpairing a vector of tuples gives a pair of vectors:

template<class L,class R>
auto unpair(std::vector<std::pair<L,R>>&& v)
{
    std::pair<std::vector<L>,std::vector<R>> out;

    for (auto& p : v)
    {
        out.first.push_back(p.first);
        out.second.push_back(p.second);
    }

    return out;
}

Variadic Mapping

Last time we discussed the Mappable type class which is similar to the Functor type class of Haskell.

When dealing with lists, Haskell also provides the zipWith function which allows you to “map” over 2 lists at once. For example, this

zipWith (+) [1,2,3] [4,5,6,7]

results in

[5,7,9]

zipWith matches each element in the same position and applies a function, in this case addition, and then constructs a new list with the results. If there is no match, extra elements are ignored. If you want to do more lists at once, there is also zipWith3, zipWith4, all the way to zipWith7.

With variadic functions and templates, the map function can be extended to generalize both map and variations of zipWith! The new mappable type class can be written as:

template<class T>
struct mappable
{
    // Type value_type
    // mappable<R> map(R(A,Args...),mappable<A>,mappable<Args>...)
    static constexpr bool is_instance = false;
};

map is now a variadic function which takes a function and at least one mappable.

Some template machinery is needed to provide underlying functionality. This will vary for different mappables, so for this post we will focus on containers.

We will want to iterate over every container at the same time, terminating whenever we reach any of the ends. This can be done using a tuple of iterators and some helper functions:

// Helper class
template<size_t index>
struct tuple_helper
{
    template<class... Args>
    static bool any_equal(const std::tuple<Args...>& lhs, const std::tuple<Args...>& rhs)
    {
        if (std::get<index>(lhs) == std::get<index>(rhs))
            return true;

        return tuple_helper<index-1>::any_equal(lhs,rhs);
    }

    template<class... Args>
    static void increment(std::tuple<Args...>& a)
    {
        tuple_helper<index-1>::increment(a);
        std::get<index>(a)++;
    }

    template<class Tuple,class... Args>
    static auto dereference(Tuple&& t, Args&&... args)
    {
        return tuple_helper<index-1>::dereference(
            std::forward<Tuple>(t),
            std::get<index>(std::forward<Tuple>(t)),
            std::forward<Args>(args)...
            );
    }
}

// Terminate template recursion
template<>
struct tuple_helper<0>
{
    template<class... Args>
    static bool any_equal(const std::tuple<Args...>& lhs, const std::tuple<Args...>& rhs)
    {
        return std::get<0>(lhs) == std::get<0>(rhs);
    }

    template<class... Args>
    static void increment(std::tuple<Args...>& a)
    {
        std::get<0>(a)++;
    }

    template<class Tuple,class... Args>
    static auto dereference(Tuple&& t, Args&&... args)
    {
        return std::tuple<decltype(*std::get<0>(t)),decltype(*args)...>(
            *std::get<0>(t),(*args)...);
    }
}

// Check if any tuple elements are equal
template<class A,class... Args>
bool tuple_any_equal(const std::tuple<A,Args...>& lhs, const std::tuple<A,Args...>& rhs)
{
    return tuple_helper<sizeof...(Args)>::any_equal(lhs,rhs);
}

// Increment all tuple elements
template<class A,class... Args>
void tuple_increment(std::tuple<A,Args...>& a)
{
    tuple_helper<sizeof...(Args)>::increment(a);
}

// Dereference iterators
template<class Tuple>
auto tuple_dereference(Tuple&& t)
{
    return tuple_helper<std::tuple_size<typename std::remove_reference<Tuple>::type>::value-1>
        ::dereference(std::forward<Tuple>(t));
}

These functions essentially allow us to write a for loop over multiple containers at the same time by packing iterators into a tuple.

In combination with tuple forwarding, we can write some pretty neat code. To replicate the Haskell example above:

int main()
{
    std::vector<int> a{1,2,3};
    std::vector<int> b{4,5,6,7};

    const auto ends = std::make_tuple(a.end(),b.end());
    for (auto iters = std::make_tuple(a.begin(),b.begin());
         !tuple_any_equal(iters,ends);
         tuple_increment(iters))
    {
        std::cout << tuple_eval(std::plus<int>(),tuple_dereference(iters)) << " ";
    }

    return 0;
}

Which outputs:

5 7 9

Of course, we want to hide all of that iterator business away inside of the map function. Thus we can rewrite the container mappable instance like this:

template<class T>
struct default_container_mappable
{
    // Type value_type
    using value_type = typename container_traits<T>::value_type;

    // mappable<R> map(R(A,Args...),mappable<A>,mappable<Args>...)
    template<class F,class A,class... Args>
    static auto map(F&& f, const A& in, const Args&... args)
        -> typename container_traits<T>::template rebind<
            decltype(eval(f,
                std::declval<typename container_traits<A>::value_type>(),
                std::declval<typename container_traits<Args>::value_type>()...
                ))>
    {
        using B = decltype(eval(f,
            std::declval<typename container_traits<A>::value_type>(),
            std::declval<typename container_traits<Args>::value_type>()...
            ));
        using T_B = typename container_traits<T>::template rebind<B>;

        T_B out;

        const auto ends = std::make_tuple(in.end(),(args.end())...);

        for (auto iters = std::make_tuple(in.begin(),(args.begin())...);
             !tuple_any_equal(iters,ends);
             tuple_increment(iters))
        {
            container_traits<T_B>::add_element(out,
                tuple_eval(std::forward<F>(f),tuple_dereference(iters)));
        }

        return out;
    }

    static constexpr bool is_instance = true;
};

// variadic convenience function
template<class F, class T, class... Args>
auto map(F&& f, const T& in, const Args&... args)
{
    return mappable<T>::map(std::forward<F>(f),in,args...);
}

And we can simply write:

int main()
{
    std::vector<int> a{1,2,3};
    std::vector<int> b{4,5,6,7};

    for (int n : map(std::plus<int>(),a,b))
        std::cout << n << " ";

    return 0;
}

You can do this for any instance of mappable, though it’s sometimes tricky. For instance, the function instance makes use of multi_tuple_eval to evaluate multiple functions with multiple parameters.

The full code and examples for std::shared_ptr and functions are available here.

Type Class – Mappable

Previously, we have introduced the concept of type classes with the monoid. The next type class to look at is the mappable type class, representing “things” that can be mapped. This class is quite similar to the Functor type class in Haskell.

An instance of mappable is something that can be queried for values, such as std::vector, std::shared_ptr or std::function. The function map basically lets you transform the values of a query. It is essentially a generalized functional style std::transform.

Mapping becomes an even more powerful as our repertoire of type classes expands, especially with folding and filtering, but let’s not get ahead of ourselves.

The mappable type class:

template<class T>
struct mappable
{
    // Type value_type
    // mappable<R> map(R(A),mappable<A>)
    static constexpr bool is_instance = false;
};

The type class lets you determine the result of a query to a mappable using value_type. It also contains the map function, which is specialized by each instance.

Mapping a function (or function-like object) will return a new function with its return value modified:

template<class Result,class... Params>
struct mappable<Result(Params...)>
{
    // Type value_type
    using value_type = Result;

    // mappable<R> map(R(A),mappable<A>)
    template<class F,class A>
    static auto map(F&& f, const A& in)
    {
        return [=](Params... params)
        {
            return eval(f,eval(in,std::forward<Params>(params)...));
        };
    }

    static constexpr bool is_instance = true;
};

// const member function
template<class Result, class Class, class... Params>
struct mappable<Result(Class::*)(Params...) const> :
    public mappable<Result(const Class&,Params...)>
{};

// member function
template<class Result, class Class, class... Params>
struct mappable<Result(Class::*)(Params...)> :
    public mappable<Result(Class&,Params...)>
{};

// member object
template<class Result, class Class>
struct mappable<Result(Class::*)> :
    public mappable<Result(const Class&)>
{};

// free function
template<class Result, class... Params>
struct mappable<Result(*)(Params...)> :
    public mappable<Result(Params...)>
{};

Notice that the Result type doesn’t matter for the purposes of map, only the parameters (Params...) do. For example:

template<int X>
int increment_by(int n){return n+X;}

// still returns an integer
auto func = mappable<char(const std::string&)>::map(&increment_by<1>,&std::string::size);

We have to specify const std::string& because we can’t turn Params... into universal references, though that would be a nice improvement.

Generally, it’s the “shape” of the mappable that determines what can be mapped. For functions, the parameters types determine the shape. For pointers, it might be the particular type of pointer. For containers, it would be the type of container used.

To reflect this, we will make use of container_traits to write the container instances:

template<class T>
struct default_container_mappable
{
    // Type value_type
    using value_type = typename container_traits<T>::value_type;

    // mappable<R> map(R(A),mappable<A>)
    template<class F,class A>
    static auto map(F&& f, const A& in)
        -> typename container_traits<T>::template rebind<
            decltype(eval(f,std::declval<typename container_traits<A>::value_type>()))>
    {
        using B = decltype(eval(f,std::declval<typename container_traits<A>::value_type>()));
        using T_B = typename container_traits<T>::template rebind<B>;

        T_B out;

        for (auto& a : in)
            container_traits<T_B>::add_element(out,eval(std::forward<F>(f),a));

        return out;
    }

    static constexpr bool is_instance = true;
};

#define FC_DEFAULT_CONTAINER_MAPPABLE(T)\
    template<class... Args>\
    struct mappable<T<Args...>> : public default_container_mappable<T<Args...>>\
    {};

FC_DEFAULT_CONTAINER_MAPPABLE(std::deque);
FC_DEFAULT_CONTAINER_MAPPABLE(std::list);
FC_DEFAULT_CONTAINER_MAPPABLE(std::multiset);
FC_DEFAULT_CONTAINER_MAPPABLE(std::set);
FC_DEFAULT_CONTAINER_MAPPABLE(std::basic_string);
FC_DEFAULT_CONTAINER_MAPPABLE(std::unordered_multiset);
FC_DEFAULT_CONTAINER_MAPPABLE(std::unordered_set);
FC_DEFAULT_CONTAINER_MAPPABLE(std::vector);

As with functions, the type of container passed in doesn’t matter. The actual type returned by map has the same “shape” as specified in the specific instance of mappable, but rebound to a new value_type.

If you want to just keep the same “shape”, a convenience function can be used which automatically determines the output:

template<class F, class T>
auto map(F&& f, const T& in)
{
    return mappable<T>::map(std::forward<F>(f),in);
}

To demonstrate how mappable can be used:

int main()
{
    // function
    std::string words = "hello, world!";
    auto string_length_plus_one = 
        mappable<char(const std::string&)>::map(&increment_by<1>,&std::string::size);
    std::cout << "size + 1:         " << string_length_plus_one(words) << "\n";

    // container with convenience function
    auto shout = [](char c){return std::toupper(c,std::locale::classic());};
    std::cout << "shout:            " << map(shout,words) << "\n";

    // container to different container
    std::cout << "characters used:  ";
    for (char c : mappable<std::set<char>>::map([](char a){return a;},words))
        std::cout << "(" << c << ") ";
    std::cout << "\n";

    return 0;
}

Which gives the output:

size + 1:         14
shout:            HELLO, WORLD!
characters used:  ( ) (!) (,) (d) (e) (h) (l) (o) (w)

Working code available here, with a few more examples too!

Note: It goes without saying that you shouldn’t combine this with using namespace std because of std::map.