Functional C++
source link: https://functionalcpp.wordpress.com/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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!
Written by whanhee 1 Comment Posted in Uncategorized Tagged with c++, c++11, c++14, Continuation passing style, cpp, CPS, functional programming, higher order function 2013/11/19
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_cps = [](
auto
&& k){
return
k(1);};
// Also prints 1
one_cps(show);
The one_cps
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_cps = []<
class
T>(
const
T& lhs,
const
T& rhs,
auto
&& k)
{
return
k(lhs+rhs);
};
auto
sub_cps = []<
class
T>(
const
T& lhs,
const
T& rhs,
auto
&& k)
{
return
k(lhs-rhs);
};
auto
mul_cps = []<
class
T>(
const
T& lhs,
const
T& rhs,
auto
&& k)
{
return
k(lhs*rhs);
};
auto
div_cps = []<
class
T>(
const
T& lhs,
const
T& rhs,
auto
&& k)
{
return
k(lhs/rhs);
};
auto
eq_cps = []<
class
T>(
const
T& lhs,
const
T& rhs,
auto
&& k)
{
return
k(lhs==rhs);
};
// etc...
add_cps(1,2,show);
// prints 3
times_cps(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_cps = [&]<
class
T>(
const
T& lhs,
const
T& rhs,
auto
&& k)
{
return
mul_cps(lhs,lhs,[&](
const
T& lhs2){
return
mul_cps(rhs,rhs,[&](
const
T& rhs2){
return
add_cps(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_cps
which is used to square the left number:
return
mul_cps(lhs,lhs,
// ...
);
The next layer is the continuation of the first layer:
[&](
const
T& lhs2){
return
mul_cps(rhs,rhs,
// ....
}
As with the outer layer, we are using mul_cps
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_cps(lhs2,rhs2,k);
}
We capture lhs2
and finally compute the sum of the squares using add_cps
. As this is the final result of the computation, the continuation is that of the entire sum_of_squares_cps
function.
The function can then be used as expected:
sum_or_squares_cps(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_cps =
[&](
int
n,
const
std::function<
void
(
int
)>& k){
eq_cps(n,0,[&](
bool
done){
if
(done)
k(1);
else
sub_cps(n,1,[&](
int
m){
factorial_cps(m,[&](
int
p){
mul_cps(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.
Edit (2015-01-15): Changed function suffixes to _cps
.
Written by whanhee 6 Comments Posted in Functions Tagged with Continuation passing style, CPS, functional programming 2013/10/22
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.
Written by whanhee 2 Comments Posted in Data Tagged with c++, cpp, filterable, functional programming, type class 2013/10/05
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!
Written by whanhee Leave a comment Posted in Data Tagged with c++, cpp, fold, functional programming, type class 2013/09/18
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!
Written by whanhee Leave a comment Posted in Data Tagged with c++, cpp, foldable, functional programming, higher order function, type class 2013/09/13
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;
}
Written by whanhee Leave a comment Posted in Data Tagged with c++, cpp, functional programming, functor, mappable, type class 2013/09/09
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.
Written by whanhee Leave a comment Posted in Data Tagged with c++, cpp, functional programming, type class 2013/09/04
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) <img width="16" height="16" class="wp-smiley emoji" draggable="false" alt="(w)" src="https://s0.wp.com/wp-content/mu-plugins/wpcom-smileys/wordpress.svg" style="height: 1em; max-height: 1em;">
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
.
Written by whanhee Leave a comment Posted in Data Tagged with c++, cpp, functional programming, functor, mappable, type class 2013/08/28
Tuple Forwarding
C++11 provides the very useful std::forward_as_tuple
function. Unfortunately, there isn’t any standard way to unpack the tuple to the parameters of a function.
To do this, template recursion and forwarding can be used. Recursing over a tuple allows for the extraction of the arguments, at the end eval
can evaluate the result:
template
<
size_t
index>
struct
tuple_eval_helper
{
template
<
class
Func,
class
TArgs,
class
... Args>
static
auto
evaluate(Func&& f, TArgs&& t_args, Args&&... args)
->
decltype
(tuple_eval_helper<index-1>::evaluate(
std::forward<Func>(f),
std::forward<TArgs>(t_args),
std::get<index>(std::forward<TArgs>(t_args)),
std::forward<Args>(args)...
))
{
return
tuple_eval_helper<index-1>::evaluate(
std::forward<Func>(f),
std::forward<TArgs>(t_args),
std::get<index>(std::forward<TArgs>(t_args)),
std::forward<Args>(args)...
);
}
};
template
<>
struct
tuple_eval_helper<0>
{
template
<
class
Func,
class
TArgs,
class
... Args>
static
auto
evaluate(Func&& f, TArgs&& t_args, Args&&... args)
->
decltype
(eval(
std::forward<Func>(f),
std::get<0>(std::forward<TArgs>(t_args)),
std::forward<Args>(args)...
))
{
return
eval(
std::forward<Func>(f),
std::get<0>(std::forward<TArgs>(t_args)),
std::forward<Args>(args)...
);
}
};
template
<
class
Func,
class
TArgs>
auto
tuple_eval(Func&& f, TArgs&& t_args)
->
decltype
(tuple_eval_helper<std::tuple_size<
typename
std::remove_reference<TArgs>::type>::value-1>::evaluate(
std::forward<Func>(f),
std::forward<TArgs>(t_args)
))
{
return
tuple_eval_helper<std::tuple_size<
typename
std::remove_reference<TArgs>::type>::value-1>::evaluate(
std::forward<Func>(f),
std::forward<TArgs>(t_args)
);
}
Which you can use like this:
tuple_eval(std::plus<
int
>(),std::forward_as_tuple(1,2));
Now, suppose you have a tuple of functions that you want to call with the parameters? In similar fashion, recursively extract the functions, evaluate them and forward the result to the end where they are repackaged into another tuple:
template
<
size_t
index>
struct
multi_tuple_eval_helper
{
template
<
class
TFuncs,
class
TArgs,
class
... Results>
static
auto
evaluate(TFuncs&& t_funcs, TArgs&& t_args, Results&&... results)
->
decltype
(multi_tuple_eval_helper<index-1>::evaluate(
std::forward<TFuncs>(t_funcs),
std::forward<TArgs>(t_args),
tuple_eval(std::get<index>(t_funcs),t_args),
std::forward<Results>(results)...
))
{
return
multi_tuple_eval_helper<index-1>::evaluate(
std::forward<TFuncs>(t_funcs),
std::forward<TArgs>(t_args),
tuple_eval(std::get<index>(t_funcs),t_args),
std::forward<Results>(results)...
);
}
};
template
<>
struct
multi_tuple_eval_helper<0>
{
template
<
class
TFuncs,
class
TArgs,
class
... Results>
static
auto
evaluate(TFuncs&& t_funcs, TArgs&& t_args, Results&&... results)
->
decltype
(std::tuple<
decltype
(tuple_eval(std::get<0>(t_funcs),t_args)),Results...>(
tuple_eval(std::get<0>(t_funcs),t_args),
std::forward<Results>(results)...
))
{
return
std::tuple<
decltype
(tuple_eval(std::get<0>(t_funcs),t_args)),Results...>(
tuple_eval(std::get<0>(t_funcs),t_args),
std::forward<Results>(results)...
);
}
};
template
<
class
TFuncs,
class
TArgs>
auto
multi_tuple_eval(TFuncs&& t_funcs, TArgs&& t_args)
->
decltype
(multi_tuple_eval_helper<std::tuple_size<
typename
std::remove_reference<TFuncs>::type>::value-1>::evaluate(
std::forward<TFuncs>(t_funcs),
std::forward<TArgs>(t_args)
))
{
return
multi_tuple_eval_helper<std::tuple_size<
typename
std::remove_reference<TFuncs>::type>::value-1>::evaluate(
std::forward<TFuncs>(t_funcs),
std::forward<TArgs>(t_args)
);
}
Which can be used like this:
multi_tuple_eval(
std::forward_as_tuple(std::plus<
int
>(),std::multiplies<
int
>()),
std::forward_as_tuple(3,4)
);
The result is the tuple (7,12)
.
Esoteric and abusive to the compiler, that’s what we’re about here at Functional C++!
Note: Be careful with move semantics and invalidating stuff when using this.
Edit: Changed multi_tuple_eval
to use the tuple constructor. It will now correctly return references.
Written by whanhee Leave a comment Posted in Functions Tagged with c++, c++11, cpp, functional programming 2013/08/22
Container Traits
The containers defined in the standard template library all provide very similar functionalities, however they are difficult to use in a generic way because of the way they are templated.
In the STL, there are a few categories of containers which behave similarly and have similar templates:
- Sequence containers take 2 arguments, the value type and an allocator. Eg.
std::vector
- Associative containers take 3 arguments, the value type, a comparison function and an allocator. Eg.
std::multiset
- Hash containers take 4 arguments, the value type, a hash, an equality test and an allocator. Eg.
std::unordered_set
- Strings take 3 arguments, the character type, character traits and an allocator. Eg.
std::wstring
Hash containers are properly called unordered associative containers, but that’s a mouth full so I will just refer to them as hash containers. To simplify the discussion, forward lists and maps will be ignored.
When dealing with containers generically, the most common things we will want to do are add an element, concatenate two containers and rebind the value type. The first two seem like no brainers, but why rebind? Suppose you are doing something like this:
template
<
class
F,
class
C>
auto
my_transform(F&& f,
const
C& c) -> OutputType
// What is this?
{
OutputType out;
for
(
const
auto
& a : c)
out.insert(eval(f,a));
return
out;
}
That code conceptually works for the associative and hash containers, which use the insert to add elements. However, in order to determine OutputType
, we would have to dig into their template parameters which would result in code which is complex at best and unmaintainable at worst.
Enter container traits:
template
<
class
C>
struct
container_traits
{
// Type value_type
// void add_element(C&,T)
// void concat(C&,C)
// Type rebind<U>
};
Here are the definitions for associative containers:
template
<
class
C>
struct
associative_container_traits;
// C: container, T: value type, O: compare, A: allocator
template
<
template
<
class
,
class
,
class
>
class
C,
class
T,
template
<
class
>
class
O,
class
A>
struct
associative_container_traits<C<T,O<T>,A>>
{
using
value_type = T;
static
void
add_element(C<T,O<T>,A>& c,
const
T& t) {c.insert(t);}
static
void
concat(C<T,O<T>,A>& lhs,
const
C<T,O<T>,A>& rhs)
{
lhs.insert(rhs.begin(),rhs.end());
}
template
<
class
U>
using
rebind = C<U,O<U>,
typename
A::
template
rebind<U>::other>;
};
template
<
class
... Args>
struct
container_traits<std::set<Args...> :
public
associative_container_traits<std::set<Args...>>
{};
template
<
class
... Args>
struct
container_traits<std::multiset<Args...> :
public
associative_container_traits<std::multiset<Args...>>
{};
Similar code is written for the sequence, hash and string containers, but I will spare you the bore.
Care must be taken to ensure that the template parameters are properly matched in rebind
. For example, the compare parameter simply substitutes its template parameter. Ideally, comparators would have their own rebind the way allocators do, however, the current code works with the default std::less
so it serves our purposes for now.
With container traits in hand, we can now write the original function, and a few others, in a very generic way:
// Transform elements in a container
template
<
class
F,
class
C>
auto
my_transform(F&& f,
const
C& c)
{
using
OutputType =
typename
container_traits<C>::
template
rebind<
decltype
(eval(f,std::declval<
typename
container_traits<C>::value_type>()))>;
OutputType out;
for
(
const
auto
& a : c)
container_traits<OutputType>::add_element(out, eval(f,a));
return
out;
}
// flattens a container of containers
template
<
class
C>
auto
flatten(
const
C& c)
{
using
OutputType =
typename
container_traits<C>::
template
rebind<
typename
container_traits<
typename
container_traits<C>::value_type>::value_type>;
OutputType out;
for
(
const
auto
& inner : c)
for
(
const
auto
& a : inner)
container_traits<OutputType>::add_element(out, a);
return
out;
}
// concatenates containers within a container
template
<
class
C>
auto
chain(
const
C& c)
{
using
OutputType =
typename
container_traits<C>::value_type;
OutputType out;
for
(
const
auto
& a : c)
container_traits<OutputType>::concat(out, a);
return
out;
}
I omit the trailing return types because they are very long and unnecessary with c++14 return type deduction.
The functions can be used like this:
int
main()
{
// words in reverse lexographic order
std::multiset<std::string,std::greater<std::string>> words{
"my"
,
"hovercraft"
,
"is"
,
"full"
,
"of"
,
"eels"
};
std::cout <<
"word lengths: "
;
for
(std::
size_t
length : my_transform(&std::string::size,words))
std::cout << length <<
" "
;
std::cout <<
"\n"
;
std::cout <<
"number of \'f\'s: "
<< flatten(words).count('f') <<
"\n"
;
auto
shout = [](
char
c){
return
std::
toupper
(c,std::locale::classic());};
std::cout <<
"yelling: "
<< my_transform(shout,chain(words)) <<
"\n"
;
return
0;
}
Output:
word lengths: 10 4 4 2 2 2
number of 'f's: 3
yelling: OFMYISHOVERCRAFTFULLEELS
You can download the complete code for this post here here.
Written by whanhee Leave a comment Posted in Data Tagged with c++, container traits, cpp, functional programming, stl
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK