# Tagged: higher order function

# Composing Continuations

We’ve seen how to use CPS and how to write new functions which combine other CPS functions. Combining functions by nesting lambdas, while neat, is pretty convoluted and an alternative way is sometimes preferred.

Previously we had something to this effect:

auto show = [](const auto& v){std::cout << v << "\n";}; auto one_cps = [](auto&& k){return k(1);}; auto double_cps = [](auto&& v, auto&& k){return k(v*2);};

And combining those to print `2`

would look something like:

auto two_cps = [&](auto&& k) { return one_cps([&](auto&& v){ return double_cps(v,k); }); }; two_cps(show); // prints 2

The benefit of nesting lambdas is that you can capture the result of previous computations. In this case, there isn’t any need for that and we can use the alternative of writing continuations which return new CPS functions.

For example, another way of writing the `double`

function would be:

auto double_cont = [](auto&& v) { return [=](auto&& k){return k(v*2);}; };

The return value looks almost exactly like `one_cps`

, but in this case, instead of `1`

we use `v*2`

.

We could get an equivalent `two_cps`

by just calling `double_cont`

with `1`

as its argument, but since this is CPS the following is far more appropriate:

// prints 4 one_cps(double_cont)(double_cont)(show);

A very important detail is that the return value of `double_cont`

captures `v`

by value. We have no way of distinguishing values that may expire by the time this function is called with its own continuation. Therefore, to use this with references, `std::ref`

and `std::cref`

are required.

These special continuation functions are actually pretty versatile and can replicate the capturing that nested lambdas do as well. All we need is a continuation that returns a continuation which returns a CPS function!

Let’s implement the `add_cont_cont`

, which has this behaviour. We want this function to return a continuation like `double_cont`

that captures one of the arguments to our operation. We want that continuation to return a CPS function.

Starting from the inside:

[=](auto&& k){return k(lhs+rhs);};

So we have a CPS function that adds 2 things. Lets write a function that will return this, but with a captured variable, just as with `double_cont`

:

[=](auto&& lhs){ return [=](auto&& k){return k(lhs+rhs);}; };

Turns out, adding more arguments is just capturing it within a lambda:

auto add_cont_cont = [](auto&& rhs) { return [=](auto&& lhs){ return [=](auto&& k){return k(lhs+rhs);}; }; };

This can be used like this:

// prints 3 one_cps(two_cps(add_cont_cont))(show);

One last concept I want to demonstrate is a sort of “meta-continuation”. A function which takes a continuation and returns another continuation but modified in a certain way.

For example this function will take a continuation, and return a continuation that applies itself twice into a CPS function:

auto twice_meta = [](auto&& cont) { return [=](auto&& v) { return [=](auto&& k) { return cont(v)(cont)(k); }; }; };

It’s return value is a typical continuation function. The innermost CPS function, however, calls the captured continuation twice before passing in the final continuation `k`

.

The final result of all of these functions is a set of easy to compose functions, albeit with a rather different syntax:

// prints 10 one_cps(twice_meta(two_cps(add_cont_cont)))(double_cont)(show);

I’ve tested on gcc-4.9, and it actually compiles down to the exact same as `std::cout << 10 << "\n";`

which is also pretty neat.

Personal statement: This post is well over a year late and for that I apologize. A lot has happened in that year but I hope to resume my postings as irregular as they may be. Thanks for reading!

# 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!