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!
Functional C++ 